The degree sequence of a scale‐free random graph process

Abstract Recently, Barabási and Albert 2 suggested modeling complex real‐world networks such as the worldwide web as follows: consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number of earlier vertices, selected with probabilities proportional to their degrees. In 2 and, with Jeong, in 3, Barabási and Albert suggested that after many steps the proportion P ( d ) of vertices with degree d should obey a power law P ( d )α d −γ . They obtained γ=2.9±0.1 by experiment and gave a simple heuristic argument suggesting that γ=3. Here we obtain P ( d ) asymptotically for all d ≤ n 1/15 , where n is the number of vertices, proving as a consequence that γ=3. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 279–290, 2001