Enumeration of Graphs with a Heavy-tailed Degree Sequence
|Room:||Mathematics (M3) 3103|
The number of graphs with a given degree sequence is still not known in any convenient form, even asymptotically, for moderately dense graphs. We obtain a formula that includes some heavy-tailed sequences in the sparse case (i.e. where the average degree is rather small).
Our general result requires upper bounds on the k-th moment of the degree sequence, for a few small integers k. Special cases include the first asymptotic enumeration results applicable to degree sequences following a power law with parameter between 2 and 3, which is the realm of empirically observed real-world networks. Another special case extends a recent result of Janson. A previous result on sparse graphs applies to a wide range of degree sequences but requires maximum degree M to the power 1/3, where M is the number of edges. Our new result applies in some cases when the maximum degree is almost the 3/5 power of M. The basic method is, as usual, that of estimating a very small probability, of the event that the random configuration model gives a simple graph.
This is joint work with Jane Gao.
200 University Avenue West
Waterloo, ON N2L 3G1