TY - JOUR

T1 - Enumeration of graphs with a heavy-tailed degree sequence

AU - Gao, Pu

AU - Wormald, Nicholas Charles

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Asymptotic enumeration of graphs

KW - Degree sequence

KW - Power law degree sequence

KW - Switchings

UR - http://www.sciencedirect.com/science/article/pii/S0001870815003382/pdfft?md5=f5ffeb3ef2b2f40e9ee42e618c7bdae8&pid=1-s2.0-S0001870815003382-main.pdf

U2 - 10.1016/j.aim.2015.09.002

DO - 10.1016/j.aim.2015.09.002

M3 - Article

VL - 287

SP - 412

EP - 450

JO - Advances in Mathematics

JF - Advances in Mathematics

SN - 0001-8708

ER -