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
A Comparison of the Degree Distribution, k-Hop Reachability, Graphlet, Closeness, and Betweenness Distributions of the Preferential Attachment Model (Red) and the Duplication Model (Blue)
© Copyright Policy
Related In: Results  -  Collection

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

pcbi-0030118-g001: A Comparison of the Degree Distribution, k-Hop Reachability, Graphlet, Closeness, and Betweenness Distributions of the Preferential Attachment Model (Red) and the Duplication Model (Blue)

Mentions: Figure 1 depicts the degree distribution, k-hop reachability, and graphlet frequency of the duplication model and the preferential attachment model with 4,902 nodes (as per the yeast PPI network [21]). Both models start with identical seed graphs; we set r = 0.12, p = 0.365 (the two key parameters of the duplication model), and c = 7 (the single key parameter of the preferential attachment model) so that the average degree of nodes in both models is seven (again as per the yeast PPI network [21]). Figure 1 compares the k-hop reachability achieved by the two models for k > 1. As can be seen, the k-hop reachability is quite different, especially for k = 3,4. Figure 1 also shows how the graphlet distributions differ, especially for dense graphlets (e.g., graphlets 17–29 and 85–145). In terms of betweenness and closeness, there are some differences as well.


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)

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

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

pcbi-0030118-g001: A Comparison of the Degree Distribution, k-Hop Reachability, Graphlet, Closeness, and Betweenness Distributions of the Preferential Attachment Model (Red) and the Duplication Model (Blue)
Mentions: Figure 1 depicts the degree distribution, k-hop reachability, and graphlet frequency of the duplication model and the preferential attachment model with 4,902 nodes (as per the yeast PPI network [21]). Both models start with identical seed graphs; we set r = 0.12, p = 0.365 (the two key parameters of the duplication model), and c = 7 (the single key parameter of the preferential attachment model) so that the average degree of nodes in both models is seven (again as per the yeast PPI network [21]). Figure 1 compares the k-hop reachability achieved by the two models for k > 1. As can be seen, the k-hop reachability is quite different, especially for k = 3,4. Figure 1 also shows how the graphlet distributions differ, especially for dense graphlets (e.g., graphlets 17–29 and 85–145). In terms of betweenness and closeness, there are some differences as well.

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