Are randomly grown graphs really random?
Physical Review E, 64 (4):
041902+ (14.06.2001)DOI: 10.1103/physreve.64.041902
Аннотация
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.