ESTIMATING AND UNDERSTANDING EXPONENTIAL RANDOM GRAPH MODELS

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.