Estimating and understanding exponential random graph models

By Sourav Chatterjee, Persi Diaconis. 2011

373 citations recorded by the source corpus.

We introduce a method for the theoretical analysis of exponential random graph models. The method is based on a large-deviations approximation to the normalizing constant shown to be consistent using theory developed by Chatterjee and Varadhan [European J. Combin. 32 (2011) 1000-1017]. The theory explains a host of difficulties encountered by applied workers: many distinct models have essentially the same MLE, rendering the problems ``practically'' ill-posed. We give the first rigorous proofs of ``degeneracy'' observed in these models. Here, almost all graphs have essentially no edges or are essentially complete. We supplement recent work of Bhamidi, Bresler and Sly [2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2008) 803-812 IEEE] showing that for many models, the extra sufficient statistics are useless: most realizations look like the results of a simple Erd\H{o}s-R\'{e}nyi model. We also find classes of models where the limiting graphs differ from Erd\H{o}s-R\'{e}nyi graphs. A limitation of our approach, inherited from the limitation of graph limit theory, is that it works only for dense graphs.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/09350843d21273d36caf22675cb588f88c518462

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Statistical and Nonlinear Physics

Citations in the corpus

Nonlinear large deviations (2014, background): “The mathematical problem was solved in [11] where it was shown that if Z N is the normalizing constant, then as N goes to inﬁnity (keeping β 1 , . . . , β l are ﬁxed), where P N denotes the set P deﬁned in Subsection 1.3, that is, the set of all x = ( x ij ) 1 ≤ i j ≤ N with x ij ∈ [0 , 1] for all…”
An introduction to large deviations for random graphs (2016, methodology): “The following theorem was proved in [19].”
The statistical physics of real-world networks (2018, methodology): “[134] S.”
Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations (2016, background): “The graph G is referred to in the literature as an exponential random graph (see e.g. Chatterjee and Diaconis [2013] and references therein).”
The sample size required in importance sampling (2015, background): “Recently, a variety of exponential random graph models have been explicitly ‘solved’ (see Chatterjee and Diaconis [16], Kenyon, Radin, Ren and Sadun [35], Kenyon and Yin [36] and Bhattacharya, Ganguly, Lubetzky and Zhao [6]).”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “They have also appeared recently in large deviations [32, 33, 70] and mathematical statistics [30, 81].”
A tensor approach to learning mixed membership community models (2013, neutral): “…we have E[(Gα0X,A) ⊤|ΠA,ΠX ] = FADiag(α̂1/2)ΨX , (16) E[Tα0X→{A,B,C} |ΠA,ΠB ,ΠC ] = k∑ i=1 α̂i(FA)i ⊗ (FB)i ⊗ (FC)i, (17) where (FA)i corresponds to i th column of FA and ΨX relates to the community membership matrix ΠX as ΨX := Diag(α̂ −1/2) ( √ α0 + 1ΠX − ( √ α0 + 1− 1) ( 1 |X| ∑ i∈X πi ) ~1⊤ ) .”
Upper tails via high moments and entropic stability (2019, background): “o occur|that is, when X() ˝(E[X])2=Var(X). Other random graph models. Upper tails for subgraph counts have been considered in random graph models other than G n;p, such as exponential random graphs [18], random geometric graphs [19], random regular graphs [60], and (dense) uniform random graphs [24]”
Econometrics of Network Formation (2016, background): “Recent work by Bhamidi, Bresler, and Sly (2008) and Chatterjee and Diaconis (2013) has clarified exactly why these problems happen in the context of dense networks.13 The MCMC procedure can only visit an infinitesimally small portion of the set of possible graphs.”