The degree sequence of a scale-free random graph process

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

Research output: Chapter in Book/Report/Conference proceedingChapter

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

Original languageEnglish (US)
Title of host publicationThe Structure and Dynamics of Networks
PublisherPrinceton University Press
Pages385-395
Number of pages11
Volume9781400841356
ISBN (Electronic)9781400841356
ISBN (Print)0691113572, 9780691113579
StatePublished - Oct 23 2011

ASJC Scopus subject areas

  • Mathematics(all)

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

    Bollobás, B., Riordan, O., Spencer, J., & Tusnády, G. (2011). The degree sequence of a scale-free random graph process. In The Structure and Dynamics of Networks (Vol. 9781400841356, pp. 385-395). Princeton University Press.