Random graphs with a given degree sequence

By Sourav Chatterjee, Persi Diaconis, Allan Sly. 2010

392 citations recorded by the source corpus.

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\'{a}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\H{o}s--Gallai characterization of degree sequences is derived.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/de425ed869760a17e81ac8256e883422b454311c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

In Statistical and Nonlinear Physics

Citations in the corpus

Random Graphs and Complex Networks (2016, background): “Alternatively, and more in the style of Luczak (1992), one can pair up all the half-edges incident to vertices of degree 2, and realize that the graph, after pairing of all the vertices of degree 2 is again a configuration model with an changed degree distribution.”
A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees (2011, methodology): “For the degree-based models considered here, [ Chatterjee et al. 11 ] gives a provably efficient iterative algorithm for computing the MLE of the β i , and uses this to study graph limits.”
Community detection in graphs (2009, background): “Nevertheless, the algorithm is quite slow, and applicable to sparse graphs with up to n ∼ 10000 vertices, with current computational resources.”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “For example, when f (x, y) is of the form ex+y/(1 + ex+y), the problem was solved in [31].”
An Econometric Model of Network Formation With Degree Heterogeneity (2017, background): “The surveys by Graham (2015) and de Paula (2016) provide additional discussion as well as references.”
Econometrics of Network Formation (2016, background): “Chatterjee et al. (2010) show that the answer is yes, and comes from the following, well-studied, model called the β-model.9 Let ν = (ν1, ..., νn) ∈ Rn and set pij = exp(νi + νj) 1 + exp(νi + νj) .”
Estimating and understanding exponential random graph models (2011, methodology): “ce, such as the degree sequence or the eigenvalues of the adjacency matrix. This allows models with suﬃcient statistics of the form Pn i=1 βidi(G) with di(G) the degree of vertex i. See, for example, [14]. These exponential models were used by Holland and Leinhardt [32] in the directed case. Frank a”