Phase transitions and other phenomena in graphs grown with preferential attachment
MetadataShow full item record
John E. Hopcroft, Andre Allavena
We study a model of grown graph where a vertex is added at each time step, then an edge is added with probability $\delta$. Callaway et al. showed that when both end vertices of the edge are chosen uniformly at random, the critical probability of edges $\delta_c$ to get a component which grows linearly with the number of vertices (a giant component) was \sfrac 1/8, smaller than in a comparable static graph. We derive a formula giving $\delta_c$ as a function of the initial self-attractiveness of vertices in a growth model where one end of the edge is chosen with preferential attachment. This number decreases even more as the self-attractiveness increases. For a self-attractiveness of one (value generally accepted for the web graph), it takes less than one edge for every twelve vertices to get a component whose size grows linearly with the number of vertices. This explains why graphs with more edges, such as the web-graph, or connectivity graphs of peer-to-peer networks, are so well connected and so well resilient to the deletion of edges. We also show how to derive a formula giving the size of this giant component as function of the number of edges and the initial attractiveness.
computer science; technical report
Previously Published As