Phase transitions and other phenomena in graphs grown with preferential 
attachment

John E. Hopcroft, Andre Allavena

Phase transitions and other phenomena in graphs grown with preferential attachment

Abstract

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.

Date Issued

2006-02-25

Publisher

Cornell University

Keywords

computer science; technical report

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2006-2018

Types

technical report