Estimating and understanding exponential random graph models

Abstract

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ős-Rényi model. We also find classes of models where the limiting graphs differ from Erdős-Rényi graphs. A limitation of our approach, inherited from the limitation of graph limit theory, is that it works only for dense graphs.

Published in at http://dx.doi.org/10.1214/13-AOS1155 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (10)

• Graph limits and exchangeable random graphs
• Solution for the properties of a clustered network
• Phase transitions in a complex network
• On replica symmetry of large deviations in random graphs
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Phase transitions in exponential random graphs
• Introduction to papers on the modeling and analysis of network data
• Estimation in spin glasses: A first step
• Critical phenomena in exponential random graphs
• Introduction to papers on the modeling and analysis of network data---II

Cited by in corpus (66)

• Matrix estimation by Universal Singular Value Thresholding
• Quantifying randomness in real networks
• Consistency under sampling of exponential random graph models
• Nonparametric Bayes dynamic modeling of relational data
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• On the Question of Effective Sample Size in Network Modeling: An Asymptotic Inquiry
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• On replica symmetry of large deviations in random graphs
• The Asymptotics of Large Constrained Graphs
• The phases of large networks with edge and triangle constraints
• Exponential Random Simplicial Complexes
• Phase transitions in exponential random graphs
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• 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
• Singularities in the entropy of asymptotically large simple graphs
• Phase transitions in social networks inspired by the Schelling model
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Ensemble nonequivalence in random graphs with modular structure
• Statistical inference for network samples using subgraph counts
• On the phase transition curve in a directed exponential random graph model
• On the lower tail variational problem for random graphs
• Logarithmic Sobolev inequalities for finite spin systems and applications
• The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems
• Large-scale estimation of random graph models with local dependence
• Interacting Thermofield Doubles and Critical Behavior in Random Regular Graphs
• Consistent structure estimation of exponential-family random graph models with block structure
• Asymptotic structure and singularities in constrained directed graphs
• Differential Calculus on Graphon Space
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Concentration inequalities for bounded functionals via generalized log-Sobolev inequalities
• Asymptotic quantization of exponential random graphs
• Motif Estimation via Subgraph Sampling: The Fourth Moment Phenomenon
• The large deviation principle for inhomogeneous Erdős-Rényi random graphs
• On the asymptotics of constrained exponential random graphs
• Reciprocity in directed networks
• Weighted Exponential Random graph models: Scope and large network limits
• Asymptotics for Sparse Exponential Random Graph Models
• Highly Scalable Maximum Likelihood and Conjugate Bayesian Inference for ERGMs on Graph Sets with Equivalent Vertices
• Atomic subgraphs and the statistical mechanics of networks
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Imaginary replica analysis of loopy regular random graphs
• The birth of geometry in exponential random graphs
• Mixing Time of Vertex-Weighted Exponential Random Graphs
• Elusive extremal graphs
• Exactly Solvable Random Graph Ensemble with Extensively Many Short Cycles
• A detailed investigation into near degenerate exponential random graphs
• On the growth rate of a linear stochastic recursion with Markovian dependence
• Non Parametric Statistics of Dynamic Networks with distinguishable nodes
• Large deviations and exact asymptotics for constrained exponential random graphs
• Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality
• Improving exponential-family random graph models for bipartite networks
• Spectral density of random graphs: convergence properties and application in model fitting
• Gradient flows on graphons: existence, convergence, continuity equations
• A Statistical Model of Bipartite Networks: Application to Cosponsorship in the United States Senate
• Modeling Heterogeneous Peer Assortment Effects using Finite Mixture Exponential Random Graph Models
• Asymptotic Structure for the Clique Density Theorem
• Block-Approximated Exponential Random Graphs
• Free-energy density functional for Strauss's model of transitive networks
• Graphical Construction of Spatial Gibbs Random Graphs
• A standard CLT for triangles in a class of ERGs
• Lattice Gas Models with Long Range Interactions
• Ground States for Exponential Random Graphs
• Longitudinal Network Models and Permutation-Uniform Markov Chains
• On the Number of Graphs with a Given Histogram
• Econometric Models of Network Formation