Are randomly grown graphs really random?

Duncan S. Callaway, John E. Hopcroft, Jon M. Kleinberg, M. E. J. Newman, and Steven H. Strogatz
Phys. Rev. E 64, 041902 – Published 20 September 2001
PDFExport Citation

Abstract

We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability δ, two vertices are chosen uniformly at random and joined by an undirected edge. This process is repeated for t time steps. In the limit of large t, the resulting graph displays surprisingly rich characteristics. In particular, a giant component emerges in an infinite-order phase transition at δ=1/8. At the transition, the average component size jumps discontinuously but remains finite. In contrast, a static random graph with the same degree distribution exhibits a second-order phase transition at δ=1/4, and the average component size diverges there. These dramatic differences between grown and static random graphs stem from a positive correlation between the degrees of connected vertices in the grown graph—older vertices tend to have higher degree, and to link with other high-degree vertices, merely by virtue of their age. We conclude that grown graphs, however randomly they are constructed, are fundamentally different from their static random graph counterparts.

  • Received 27 April 2001

DOI:https://doi.org/10.1103/PhysRevE.64.041902

©2001 American Physical Society

Authors & Affiliations

Duncan S. Callaway1, John E. Hopcroft2, Jon M. Kleinberg2, M. E. J. Newman3,4, and Steven H. Strogatz1,4

  • 1Department of Theoretical and Applied Mechanics, Cornell University, Ithaca, New York 14853-1503
  • 2Department of Computer Science, Cornell University, Ithaca, New York 14853
  • 3Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501
  • 4Center for Applied Mathematics, Cornell University, Ithaca, New York 14853-3801

References (Subscription Required)

Click to Expand
Issue

Vol. 64, Iss. 4 — October 2001

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×