title: Are randomly grown graphs really random?
abstract: We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, 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 delta=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 delta=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.
authors.affiliation: Department of Theoretical and Applied Mechanics, Cornell University, Ithaca, New York 14853-1503, USA.
authors.forename: D S
authors.initials: DS
authors.lastname: Callaway
authors.forename: J E
authors.initials: JE
authors.lastname: Hopcroft
authors.forename: J M
authors.initials: JM
authors.lastname: Kleinberg
authors.forename: M E
authors.initials: ME
authors.lastname: Newman
authors.forename: S H
authors.initials: SH
authors.lastname: Strogatz