Premium
The degree sequence of a scale‐free random graph process
Author(s) -
Bollobás B´ela,
Riordan Oliver,
Spencer Joel,
Tusnády Gábor
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.1009
Subject(s) - random graph , combinatorics , mathematics , graph , degree (music) , random regular graph , preferential attachment , discrete mathematics , sequence (biology) , complex network , line graph , physics , genetics , 1 planar graph , biology , acoustics
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