The degree sequence of a scale‐free random graph process

TLDR

Barabási and Albert proposed modeling complex networks by adding vertices one at a time and linking them preferentially to high‑degree vertices, predicting a power‑law degree distribution P(d)∝d^−γ. This work derives the asymptotic degree distribution P(d) for all d ≤ n^{1/15} and proves that the exponent γ equals 3. Experimental measurements gave γ≈2.9±0.1, and the analysis confirms γ=3 for the specified degree range. © 2001 John Wiley & Sons, Inc., Random Structures & Algorithms 18:279–290.

Abstract

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