Enumeration of graphs with a heavy-tailed degree sequence

DOI10.1016/J.AIM.2015.09.002zbMATH Open1327.05155arXiv1404.1250OpenAlexW2963217502MaRDI QIDQ895547FDOQ895547

Authors: Pu Gao, Nicholas Wormald 

Publication date: 3 December 2015

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: In this paper, we asymptotically enumerate graphs with a given degree sequence d=(d_1,...,d_n) 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 M_k= sum_{i=1}^n [d_i]_k for a few small integers kge 1. Note that M_1 is simply the total degree of the graphs. As special cases, we asymptotically enumerate graphs with (i) degree sequences satisfying M_2=o(M_1^{ 9/8}); (ii) degree sequences following a power law with parameter gamma>5/2; (iii) power-law degree sequences that mimic independent power-law "degrees" with parameter gamma>1+sqrt{3}approx 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 Delta =o(M_1^{1/3}), where Delta is the maximum degree. Our new result applies in some cases when Delta is only barely o(M_1^ {3/5}). Case (i) above generalises a result of Janson which requires M_2=O(M_1) (and hence M_1=O(n) and Delta=O(n^{1/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<gamma<3.

Full work available at URL: https://arxiv.org/abs/1404.1250

Recommendations

• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• scientific article; zbMATH DE number 747040
• On the asymptotics of degree structure of configuration graphs with bounded number of edges
• Asymptotic enumeration of graphs with given degree sequence

zbMATH Keywords

degree sequenceswitchingsasymptotic enumeration of graphspower law degree sequence

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30)

Cites Work

• Statistical mechanics of complex networks
• Title not available (Why is that?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The degree sequence of a scale-free random graph process
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees
• The probability that a random multigraph is simple
• A general model of web graphs
• On a conjecture related to geometric routing
• The asymptotic number of labeled graphs with given degree sequences
• A Random Graph Model for Power Law Graphs
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The probability that a random multigraph is simple. II
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)

Cited In (12)

• Counting deranged matchings
• Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
• The mixing time of switch Markov chains: a unified approach
• Limit laws for self-loops and multiple edges in the configuration model
• Mixing time of the swap Markov chain and \(P\)-stability
• When is a scale-free graph ultra-small?
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝)
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Mixing time of the switch Markov chain and stable degree sequences
• Random graphs with given vertex degrees and switchings
• Threshold functions for small subgraphs in simple graphs and multigraphs
• The switch Markov chain for sampling irregular graphs and digraphs

This page was built for publication: Enumeration of graphs with a heavy-tailed degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q895547)