Random graphs with a given degree sequence

Abstract

Large graphs are sometimes studied through their degree sequences (power law or regular graphs). We study graphs that are uniformly chosen with a given degree sequence. Under mild conditions, it is shown that sequences of such graphs have graph limits in the sense of Lovász and Szegedy with identifiable limits. This allows simple determination of other features such as the number of triangles. The argument proceeds by studying a natural exponential model having the degree sequence as a sufficient statistic. The maximum likelihood estimate (MLE) of the parameters is shown to be unique and consistent with high probability. Thus $n$ parameters can be consistently estimated based on a sample of size one. A fast, provably convergent, algorithm for the MLE is derived. These ingredients combine to prove the graph limit theorem. Along the way, a continuous version of the Erdős--Gallai characterization of degree sequences is derived.

Published in at http://dx.doi.org/10.1214/10-AAP728 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Graph limits and exchangeable random graphs
• On exchangeable random variables and the statistics of large graphs and hypergraphs

Cited by in corpus (29)

• Matrix estimation by Universal Singular Value Thresholding
• Estimating and understanding exponential random graph models
• Quantifying randomness in real networks
• Consistency under sampling of exponential random graph models
• Maximum lilkelihood estimation in the $\beta$-model
• A central limit theorem in the $\beta$-model for undirected random graphs with a diverging number of vertices
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• On the Question of Effective Sample Size in Network Modeling: An Asymptotic Inquiry
• Inference using noisy degrees: Differentially private $\beta$-model and synthetic graphs
• Statistical Modelling of Citation Exchange Between Statistics Journals
• Asymptotic normality in the maximum entropy models on graphs with an increasing number of parameters
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Complex martingales and asymptotic enumeration
• Consistent structure estimation of exponential-family random graph models with block structure
• Random Simplicial Complexes: Models and Phenomena
• Motif Estimation via Subgraph Sampling: The Fourth Moment Phenomenon
• On the asymptotics of constrained exponential random graphs
• The $\beta$-model for Random Graphs --- Regression, Cramér-Rao Bounds, and Hypothesis Testing
• Multigraph limit of the dense configuration model and the preferential attachment graph
• Edge differentially private estimation in the $\beta$-model via jittering and method of moments
• Time-varying $\beta$-model for dynamic directed networks
• Statistical field theory of random graphs with prescribed degrees
• Embedding theorems for random graphs with specified degrees
• Marked random graphs with given degree sequence: large deviations on the local topology
• On the Number of Graphs with a Given Histogram
• Learning to sample fibers for goodness-of-fit testing
• Econometric Models of Network Formation