Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2007 Jul;3(7):e118.
doi: 10.1371/journal.pcbi.0030118.

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

Fereydoun Hormozdiari  1 , Petra Berenbrink, Natasa Przulj, S Cenk Sahinalp
Affiliations

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

Fereydoun Hormozdiari et al. PLoS Comput Biol. 2007 Jul.

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.

PubMed Disclaimer

Conflict of interest statement

Competing interests. The authors have declared that no competing interests exist.

Figures

Figure 1
Figure 1. 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)
Figure 2
Figure 2. The Effect of the Seed Graph on the Degree Distribution, k-Hop Reachability, Graphlet, Closeness, and Betweenness Distributions of the Duplication Model
Each color (red, blue, green) depicts the behavior of a network with a particular seed graph. The parameters p and r are identical in all three models.
Figure 3
Figure 3. 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)
Figure 4
Figure 4. The Topological Properties of the Duplication Model (Blue) and Preferential Attachment Model (Green) Compared with That of the CORE Yeast PPI Network (Red)
The degree distribution, the k-hop reachability, graphlet, closeness, and betweenness distributions of both networks are shown.
Figure 5
Figure 5. Comparison of Duplication (Blue) and Preferential Attachment (Green) with 70% Bait and 70% Edge Coverage against the Yeast PPI Network (Red)
Figure 6
Figure 6. Comparison of Duplication (Blue) and Preferential Attachment (Green) with 50% Bait and 50% Edge Coverage against the CORE Yeast PPI Network (Red)
Figure 7
Figure 7. A Comparison of the Yeast PPI Network (Red) and (Five Independent Runs of) the Erdos–Renyi Random Graph Model (Green)
See this image and copyright information in PMC

References

    1. Jeong H, Mason S, Barabási AL, Oltvai ZN. Lethality and centrality in protein networks. Nature. 2001;411:41. - PubMed
    1. Wagner A. The Yeast protein interaction network evolves rapidly and contains few redundant duplicate genes. Mol Biol Evol. 2001;18:1283–1292. - PubMed
    1. Han J, Dupuy D, Bertin N, Cusick M, Vidal M. Effect of sampling on topology predictions of protein–protein interaction networks. Nature Biotech. 2005;23:839–844. - PubMed
    1. Przulj N, Corneil DG, Jurisica I. Modeling interactome: Scale-free or geometric? Bioinformatics. 2005;150:216–231. - PubMed
    1. Tanaka R, Yi TM, Doyle J. Some protein interaction data do not exhibit power law statistics. FEBS Letters. 2005;579:5140–5144. - PubMed

LinkOut - more resources