Estimating and understanding exponential random graph models
S. Chatterjee, and P. Diaconis. (2011)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).
DOI: 10.1214/13-AOS1155
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\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.
Description
Estimating and understanding exponential random graph models
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)
%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
}