Not all scale-free networks are born equal: the role of the seed graph in PPI network evolution.
Bottom Line:
The (asymptotic) degree distributions of the best-known "scale-free" network models are all similar and are independent of the seed graph used; hence, it has been tempting to assume that networks generated by these models are generally similar.In this paper, we observe that several key topological features of such networks depend heavily on the specific model and the seed graph used.Furthermore, we show that starting with the "right" seed graph (typically a dense subgraph of the protein-protein interaction network analyzed), the duplication model captures many topological features of publicly available protein-protein interaction networks very well.
View Article:
PubMed Central - PubMed
Affiliation: School of Computing Science, Simon Fraser University, Burnaby, British Columbia, Canada.
ABSTRACT
Show MeSH
The (asymptotic) degree distributions of the best-known "scale-free" network models are all similar and are independent of the seed graph used; hence, it has been tempting to assume that networks generated by these models are generally similar. In this paper, we observe that several key topological features of such networks depend heavily on the specific model and the seed graph used. Furthermore, we show that starting with the "right" seed graph (typically a dense subgraph of the protein-protein interaction network analyzed), the duplication model captures many topological features of publicly available protein-protein interaction networks very well. |
Related In:
Results -
Collection
License getmorefigures.php?uid=PMC1913096&req=5
Mentions: As mentioned before, there are two key parameters associated with the duplication model: p, the edge maintenance probability; and r, the edge insertion probability. These two parameters alone determine the (asymptotic) degree distribution and the average degree of the generated network. We chose p = 0.365 and r = 0.12 so that the degree distribution of the duplication model matches that of the yeast PPI network (see Methods and Materials for the exact mathematical expressions for p and r). Also, for the preferential attachment model, we choose the value c = 7 so that the average degree of the graph created using preferential attachment would be equal to that of the yeast PPI network. We used the duplication model and preferential attachment model described above to generate a network with 4,902 nodes. The resulting networks are compared with the yeast PPI network in terms of the k-hop reachability, the graphlet, betweenness, and closeness distributions in Figure 3. Under all these measures, the yeast PPI network is very similar to the network produced by the duplication model (and not similar to the network produced by the preferential attachment model). In fact, the duplication model approximates both the k-hop degree distribution and the graphlet distribution of the yeast network much better than the random graph models described earlier in the literature ([4] and [19])—which were specifically devised to capture the respective features of the yeast PPI network. |
View Article: PubMed Central - PubMed
Affiliation: School of Computing Science, Simon Fraser University, Burnaby, British Columbia, Canada.