Limit laws for self-loops and multiple edges in the configuration model

DOI10.1214/18-AIHP926MaRDI QIDQ2337833zbMATH OpenFDO

Authors Omer Angel, Remco van der Hofstad, Cecilia Holmgren

Publication date 20 November 2019

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.07172, https://projecteuclid.org/euclid.aihp/1569398877

zbMATH Keywords

Chen-Stein Poisson approximationconfiguration modelmultiple edgesself-loops

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Processes in random environments (60K37) Percolation (82B43)

Abstract: We consider self-loops and multiple edges in the configuration model as the size of the graph tends to infinity. The interest in these random variables is due to the fact that the configuration model, conditioned on being simple, is a uniform random graph with prescribed degrees. Simplicity corresponds to the absence of self-loops and multiple edges. We show that the number of self-loops and multiple edges converges in distribution to two independent Poisson random variables when the second moment of the empirical degree distribution converges. We also provide an estimate on the total variation distance between the number of self-loops and multiple edges and the Poisson limit of their sum. This revisits previous works of Bollob'as, of Janson, of Wormald and others. The error estimates also imply sharp asymptotics for the number of simple graphs with prescribed degrees. The error estimates follow from an application of Stein's method for Poisson convergence, which is a novel method for this problem. The asymptotic independence of self-loops and multiple edges follows from a Poisson version of the Cram'er-Wold device using thinning, which is of independent interest. When the degree distribution has infinite second moment, our general results break down. We can, however, prove a central limit theorem for the number of self-loops, and for the multiple edges between vertices of degrees much smaller than the square root of the size of the graph, or when we truncate the degrees similarly. Our results and proofs easily extend to directed and bipartite configuration models.

Recommendations

• Limit distributions of the number of loops in a random configuration graph
• Counting graphs and null models of complex networks: configuration model and extensions
• Limit distributions of the number of vertices of a given degree in a configuration graph with bounded number of edges
• On the limit distributions of the degrees of vertices in configuration graphs with a bounded number of edges
• Directed random graphs with given degree distributions

Cites work

• A critical point for random graphs with a given degree sequence
• 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})\)
• Characterizing optimal sampling of binary contingency tables via the configuration model
• Enumeration of graphs with a heavy-tailed degree sequence
• Generating simple random graphs with prescribed degree distribution
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• Law of large numbers for the SIR epidemic on a random graph with given degrees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Random graphs and complex networks. Volume 1
• Statistical mechanics of complex networks
• The asymptotic distribution of short cycles in random regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The probability that a random multigraph is simple
• The probability that a random multigraph is simple. II
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The Structure and Function of Complex Networks
• Upper bounds for number of removed edges in the erased configuration model
• Using Stein's method to show Poisson and normal limit laws for fringe subtrees
• When is a scale-free graph ultra-small?

Cited in

(16)

• Central limit theorems in the configuration model
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Limit distributions of the number of loops in a random configuration graph
• Upper bounds for number of removed edges in the erased configuration model
• I/O-efficient generation of massive graphs following the \textit{LFR} benchmark
• Limit theorems for assortativity and clustering in null models for scale-free networks
• Glauber dynamics for Ising models on random regular graphs: cut-off and metastability
• Moments of uniform random multigraphs with fixed degree sequences
• Asymptotic normality in random graphs with given vertex degrees
• Central limit theorem for statistics of subcritical configuration models
• Phase transition in random intersection graphs with communities
• scientific article; zbMATH DE number 7731163 (Why is no real title available?)
• Multiscale genesis of a tiny giant for percolation on scale-free random graphs
• Randomized algorithms to generate hypergraphs with given degree sequences
• Dynamic random intersection graph: dynamic local convergence and giant structure
• Poisson approximation for cycles in the generalised random graph

This page was built for publication: Limit laws for self-loops and multiple edges in the configuration model

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