Enumeration of graphs with a heavy-tailed degree sequence
From MaRDI portal
Publication:895547
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.
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
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 5485446 (Why is no real title available?)
- scientific article; zbMATH DE number 3906527 (Why is no real title available?)
- A Brief History of Generative Models for Power Law and Lognormal Distributions
- A Random Graph Model for Power Law Graphs
- A general model of web graphs
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- On a conjecture related to geometric routing
- Random hyperbolic graphs: degree sequence and clustering (extended abstract)
- Statistical mechanics of complex networks
- The Volume of the Giant Component of a Random Graph with Given Expected Degrees
- The asymptotic number of labeled graphs with given degree sequences
- The degree sequence of a scale-free random graph process
- The probability that a random multigraph is simple
- The probability that a random multigraph is simple. II
Cited in
(13)- When is a scale-free graph ultra-small?
- Mixing time of the swap Markov chain and \(P\)-stability
- Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
- Random graphs with given vertex degrees and switchings
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Asymptotic enumeration of graphs with given degree sequence
- Threshold functions for small subgraphs in simple graphs and multigraphs
- The mixing time of switch Markov chains: a unified approach
- Limit laws for self-loops and multiple edges in the configuration model
- Counting deranged matchings
- Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
- The switch Markov chain for sampling irregular graphs and digraphs
- Mixing time of the switch Markov chain and stable degree sequences
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)
