Enumeration of graphs with a heavy-tailed degree sequence

Research output: Contribution to journalArticleResearchpeer-review

15 Citations (Scopus)

Abstract

In this paper, we asymptotically enumerate graphs with a given degree sequence d=(d1, . . ., dn) satisfying restrictions designed to permit heavy-tailed sequences in the sparse case (i.e. where the average degree is rather small). Our general result requires upper bounds on functions of Mk=∑i=1 n[di]k for a few small integers k≥1. Note that M1 is simply the total degree of the graphs. As special cases, we asymptotically enumerate graphs with (i) degree sequences satisfying M2=o(M1 9/8); (ii) degree sequences following a power law with parameter γ>5/2; (iii) power-law degree sequences that mimic independent power-law "degrees" with parameter γ>1+3≈2.732; (iv) degree sequences following a certain "long-tailed" power law; (v) certain bi-valued sequences. A previous result on sparse graphs by McKay and the second author applies to a wide range of degree sequences but requires δ=o(M1 1/3), where δ is the maximum degree. Our new result applies in some cases when δ is only barely o(M1 3/5). Case (i) above generalises a result of Janson which requires M2=O(M1) (and hence M1=O(n) and δ=O(n1/2)). Cases (ii) and (iii) provide the first asymptotic enumeration results applicable to degree sequences of real-world networks following a power law, for which it has been empirically observed that 2<γ<3.
Original languageEnglish
Pages (from-to)412-450
Number of pages39
JournalAdvances in Mathematics
Volume287
DOIs
Publication statusPublished - 2016

Keywords

  • Asymptotic enumeration of graphs
  • Degree sequence
  • Power law degree sequence
  • Switchings

Cite this