Limits...
Not all scale-free networks are born equal: the role of the seed graph in PPI network evolution.

Hormozdiari F, Berenbrink P, Przulj N, Sahinalp SC - PLoS Comput. Biol. (2007)

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
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.

Show MeSH
The Degree Distribution, the k-Hop Reachability, the Graphlet, Closeness, and Betweenness Distributions of the Yeast PPI Network (Red), Duplication Model (Blue), and Preferential Attachment Model (Green)
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC1913096&req=5

pcbi-0030118-g003: The Degree Distribution, the k-Hop Reachability, the Graphlet, Closeness, and Betweenness Distributions of the Yeast PPI Network (Red), Duplication Model (Blue), and Preferential Attachment Model (Green)

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.


Not all scale-free networks are born equal: the role of the seed graph in PPI network evolution.

Hormozdiari F, Berenbrink P, Przulj N, Sahinalp SC - PLoS Comput. Biol. (2007)

The Degree Distribution, the k-Hop Reachability, the Graphlet, Closeness, and Betweenness Distributions of the Yeast PPI Network (Red), Duplication Model (Blue), and Preferential Attachment Model (Green)
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC1913096&req=5

pcbi-0030118-g003: The Degree Distribution, the k-Hop Reachability, the Graphlet, Closeness, and Betweenness Distributions of the Yeast PPI Network (Red), Duplication Model (Blue), and Preferential Attachment Model (Green)
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.

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
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.

Show MeSH