The Diameter of a Scale-Free Random Graph
Combinatorica, 24 (1):
5--34 (January 2004)Abstract
We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabási and Albert 3, as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabási, Albert and Jeong 1,5 and heuristic arguments given by Newman, Strogatz and Watts 23 suggest that after n steps the resulting graph should have diameter approximately log n. We show that while this holds for m=1, for m=2 the diameter is asymptotically log n/log log n.
ER -
Description
Networks with power-law degree distributions have mean geodesic distances that increase no faster than log n/log log n
