Random graphs with a giüen degree sequence

Sourav Chatterjee, Persi Diaconis, Allan Sly

Research output: Contribution to journalArticle

87 Scopus citations

Abstract

Large graphs are sometimes studied through their degree sequences (power law or regular graphs). We study graphs that are uniformly chosen with a giüen degree sequence. Under mild conditions, it is shown that sequences of such graphs haüe graph limits in the sense of Loüász and Szegedy with identifiable limits. This allows simple determination of other features such as the number of triangles. The argument proceeds by studying a natural exponential model haüing the degree sequence as a sufficient statistic. The maximum likelihood estimate (MLE) of the parameters is shown to be unique and consistent with high probability. Thus n parameters can be consistently estimated based on a sample of size one. A fast, proüably conüergent, algorithm for the MLE is deriüed. These ingredients combine to proüe the graph limit theorem. Along the way, a continuous üersion of the Erdös-Gallai characterization of degree sequences is deriüed.

Original languageEnglish (US)
Pages (from-to)1400-1435
Number of pages36
JournalAnnals of Applied Probability
Volume21
Issue number4
DOIs
StatePublished - Aug 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Degree sequence
  • Erdös-Gallai criterion
  • Graph limit
  • Random graph
  • Threshold graphs

Fingerprint Dive into the research topics of 'Random graphs with a giüen degree sequence'. Together they form a unique fingerprint.

  • Cite this