%0 Generic %1 chatterjee2011estimating %A Chatterjee, Sourav %A Diaconis, Persi %D 2011 %K Exponential_random_graph entropy graphons %R 10.1214/13-AOS1155 %T Estimating and understanding exponential random graph models %U http://arxiv.org/abs/1102.2650 %X 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\Hos-Rényi model. We also find classes of models where the limiting graphs differ from Erd\Hos-Rényi graphs. A limitation of our approach, inherited from the limitation of graph limit theory, is that it works only for dense graphs.

@misc{chatterjee2011estimating, 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\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.}, added-at = {2021-12-14T12:29:57.000+0100}, author = {Chatterjee, Sourav and Diaconis, Persi}, biburl = {https://www.bibsonomy.org/bibtex/26ac25e9c543aa9a9a219815c7d66bf22/j.c.m.janssen}, description = {Estimating and understanding exponential random graph models}, doi = {10.1214/13-AOS1155}, interhash = {697a37481901a107ac74dda68572bba3}, intrahash = {6ac25e9c543aa9a9a219815c7d66bf22}, keywords = {Exponential_random_graph entropy graphons}, note = {cite arxiv:1102.2650Comment: 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)}, timestamp = {2021-12-14T12:29:57.000+0100}, title = {Estimating and understanding exponential random graph models}, url = {http://arxiv.org/abs/1102.2650}, year = 2011 }