The degree sequence of a scale-free random graph process

Béla Bollobás, Oliver Riordan, Joel Spencer, Gábor Tusnády

Research output: Contribution to journalArticle

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-y. 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 ≤ n1/15, where n is the number of vertices, proving as a consequence that γ = 3.

Original languageEnglish (US)
Pages (from-to)279-290
Number of pages12
JournalRandom Structures and Algorithms
Volume18
Issue number3
DOIs
StatePublished - May 2001

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The degree sequence of a scale-free random graph process'. Together they form a unique fingerprint.

  • Cite this