Estimating and understanding exponential random graph models. (English) Zbl 1293.62046
Summary: 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 S. Chatterjee and S. R. S. Varadhan [Eur. J. Comb. 32, No. 7, 1000–1017 (2011; Zbl 1230.05259)]. 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 S. Bhamidi, G. Bresler and A. Sly [“Mixing time of exponential random graphs”, in: 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science. Washington, DC: IEEE. 803–812 (2008; doi:10.1109/FOCS.2008.75)] showing that for many models, the extra sufficient statistics are useless: most realizations look like the results of a simple Erdos-Rényi model. We also find classes of models where the limiting graphs differ from Erdos-Rényi graphs. A limitation of our approach, inherited from the limitation of graph limit theory, is that it works only for dense graphs.
MSC:
| 62F10 | Point estimation |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 62P25 | Applications of statistics to social sciences |
| 60F10 | Large deviations |
Keywords:
random graph; Erdős-Rényi; graph limit; exponential random graph models; parameter estimationCitations:
Zbl 1230.05259Software:
tsbridgeReferences:
| [1] | Aldous, D. J. (1981). Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11 581-598. · Zbl 0474.60044 · doi:10.1016/0047-259X(81)90099-3 |
| [2] | Aristoff, D. and Radin, C. (2011). Emergent structures in large networks. Preprint. Available at . · Zbl 1276.05106 · doi:10.1239/jap/1378401243 |
| [3] | Austin, T. (2008). On exchangeable random variables and the statistics of large graphs and hypergraphs. Probab. Surv. 5 80-145. · Zbl 1189.60020 · doi:10.1214/08-PS124 |
| [4] | Austin, T. and Tao, T. (2010). Testability and repair of hereditary hypergraph properties. Random Structures Algorithms 36 373-463. · Zbl 1208.05093 · doi:10.1002/rsa.20300 |
| [5] | Besag, J. (1975). Statistical analysis of non-lattice data. Statistician 24 179-195. |
| [6] | Bhamidi, S., Bresler, G. and Sly, A. (2008). Mixing time of exponential random graphs. In 2008 IEEE 49 th Annual IEEE Symposium on Foundations of Computer Science ( FOCS ) 803-812. IEEE, Washington, DC. · Zbl 1238.60011 |
| [7] | Bollobás, B. (2001). Random Graphs , 2nd ed. Cambridge Studies in Advanced Mathematics 73 . Cambridge Univ. Press, Cambridge. · Zbl 0979.05003 |
| [8] | Bollobás, B. and Riordan, O. (2009). Metrics for sparse graphs. In Surveys in Combinatorics 2009. London Mathematical Society Lecture Note Series 365 211-287. Cambridge Univ. Press, Cambridge. · Zbl 1182.05106 |
| [9] | Borgs, C., Chayes, J., Lovász, L., Sós, V. T. and Vesztergombi, K. (2006). Counting graph homomorphisms. In Topics in Discrete Mathematics. Algorithms and Combinatorics 26 315-371. Springer, Berlin. · Zbl 1129.05050 · doi:10.1007/3-540-33700-8_18 |
| [10] | Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. (2008). Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing. Adv. Math. 219 1801-1851. · Zbl 1213.05161 · doi:10.1016/j.aim.2008.07.008 |
| [11] | Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. (2012). Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. of Math. (2) 176 151-219. · Zbl 1247.05124 · doi:10.4007/annals.2012.176.1.2 |
| [12] | Chatterjee, S. (2007). Estimation in spin glasses: A first step. Ann. Statist. 35 1931-1946. · Zbl 1126.62128 · doi:10.1214/009053607000000109 |
| [13] | Chatterjee, S. and Dey, P. S. (2010). Applications of Stein’s method for concentration inequalities. Ann. Probab. 38 2443-2485. · Zbl 1203.60023 · doi:10.1214/10-AOP542 |
| [14] | Chatterjee, S., Diaconis, P. and Sly, A. (2011). Random graphs with a given degree sequence. Ann. Appl. Probab. 21 1400-1435. · Zbl 1234.05206 · doi:10.1214/10-AAP728 |
| [15] | Chatterjee, S. and Varadhan, S. R. S. (2011). The large deviation principle for the Erdős-Rényi random graph. European J. Combin. 32 1000-1017. · Zbl 1230.05259 · doi:10.1016/j.ejc.2011.03.014 |
| [16] | Comets, F. and Janžura, M. (1998). A central limit theorem for conditionally centred random fields with an application to Markov fields. J. Appl. Probab. 35 608-621. · Zbl 0924.60026 · doi:10.1239/jap/1032265209 |
| [17] | Corander, J., Dahmström, K. and Dahmström, P. (2002). Maximum likelihood estimation for exponential random graph models. In Contributions to Social Network Analysis , Information Theory and Other Topics in Statistics : A Festschrift in Honour of Ove Frank (J. Hagberg, ed.) 1-17. Dept. Statistics, Univ. Stockholm. |
| [18] | Diaconis, P. and Janson, S. (2008). Graph limits and exchangeable random graphs. Rend. Mat. Appl. (7) 28 33-61. · Zbl 1162.60009 |
| [19] | Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 17-61. · Zbl 0103.16301 |
| [20] | Erdös, P. and Stone, A. H. (1946). On the structure of linear graphs. Bull. Amer. Math. Soc. ( N.S. ) 52 1087-1091. · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7 |
| [21] | Fienberg, S. E. (2010). Introduction to papers on the modeling and analysis of network data. Ann. Appl. Stat. 4 1-4. · doi:10.1214/10-AOAS346 |
| [22] | Fienberg, S. E. (2010). Introduction to papers on the modeling and analysis of network data-II. Ann. Appl. Stat. 4 533-534. · doi:10.1214/10-AOAS365 |
| [23] | Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971). Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22 89-103. · Zbl 0346.06011 · doi:10.1007/BF01651330 |
| [24] | Frank, O. and Strauss, D. (1986). Markov graphs. J. Amer. Statist. Assoc. 81 832-842. · Zbl 0607.05057 · doi:10.2307/2289017 |
| [25] | Freedman, M., Lovász, L. and Schrijver, A. (2007). Reflection positivity, rank connectivity, and homomorphism of graphs. J. Amer. Math. Soc. 20 37-51 (electronic). · Zbl 1107.05089 · doi:10.1090/S0894-0347-06-00529-7 |
| [26] | Frieze, A. and Kannan, R. (1999). Quick approximation to matrices and applications. Combinatorica 19 175-220. · Zbl 0933.68061 · doi:10.1007/s004930050052 |
| [27] | Gelfand, I. M. and Fomin, S. V. (2000). Calculus of Variations . Dover, New York. · Zbl 0964.49001 |
| [28] | Gelman, A. and Meng, X.-L. (1998). Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statist. Sci. 13 163-185. · Zbl 0966.65004 · doi:10.1214/ss/1028905934 |
| [29] | Geyer, C. J. and Thompson, E. A. (1992). Constrained Monte Carlo maximum likelihood for dependent data. J. R. Stat. Soc. Ser. B Stat. Methodol. 54 657-699. |
| [30] | Häggström, O. and Jonasson, J. (1999). Phase transition in the random triangle model. J. Appl. Probab. 36 1101-1115. · Zbl 0969.05055 · doi:10.1239/jap/1032374758 |
| [31] | Handcock, M. S. (2003). Assessing degeneracy in statistical models of social networks. Working Paper 39, Center for Statistics and the Social Sciences, Univ. Washington, Seattle, WA. |
| [32] | Holland, P. W. and Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76 33-65. · Zbl 0457.62090 · doi:10.2307/2287037 |
| [33] | Hoover, D. N. (1982). Row-column exchangeability and a generalized model for probability. In Exchangeability in Probability and Statistics ( Rome , 1981) 281-291. North-Holland, Amsterdam. · Zbl 0495.60040 |
| [34] | Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York. |
| [35] | Kallenberg, O. (2005). Probabilistic Symmetries and Invariance Principles . Springer, New York. · Zbl 1084.60003 |
| [36] | Kou, S. C., Zhou, Q. and Wong, W. H. (2006). Equi-energy sampler with applications in statistical inference and statistical mechanics. Ann. Statist. 34 1581-1652. · Zbl 1246.82054 · doi:10.1214/009053606000000515 |
| [37] | Lovász, L. (2006). The rank of connection matrices and the dimension of graph algebras. European J. Combin. 27 962-970. · Zbl 1088.05052 · doi:10.1016/j.ejc.2005.04.012 |
| [38] | Lovász, L. (2007). Connection matrices. In Combinatorics , Complexity , and Chance. Oxford Lecture Series in Mathematics and its Applications 34 179-190. Oxford Univ. Press, Oxford. · Zbl 1127.05064 |
| [39] | Lovász, L. and Sós, V. T. (2008). Generalized quasirandom graphs. J. Combin. Theory Ser. B 98 146-163. · Zbl 1127.05094 · doi:10.1016/j.jctb.2007.06.005 |
| [40] | Lovász, L. and Szegedy, B. (2006). Limits of dense graph sequences. J. Combin. Theory Ser. B 96 933-957. · Zbl 1113.05092 · doi:10.1016/j.jctb.2006.05.002 |
| [41] | Lovász, L. and Szegedy, B. (2007). Szemerédi’s lemma for the analyst. Geom. Funct. Anal. 17 252-270. · Zbl 1123.46020 · doi:10.1007/s00039-007-0599-6 |
| [42] | Lovász, L. and Szegedy, B. (2009). Contractors and connectors of graph algebras. J. Graph Theory 60 11-30. · Zbl 1189.05115 · doi:10.1002/jgt.20343 |
| [43] | Lovász, L. and Szegedy, B. (2010). Testing properties of graphs and functions. Israel J. Math. 178 113-156. · Zbl 1246.05106 · doi:10.1007/s11856-010-0060-7 |
| [44] | Lubetzky, E. and Zhao, Y. (2012). On replica symmetry of large deviations in random graphs. Preprint. Available at . · Zbl 1348.05195 |
| [45] | Park, J. and Newman, M. E. J. (2004). Solution of the two-star model of a network. Phys. Rev. E (3) 70 066146, 5. |
| [46] | Park, J. and Newman, M. E. J. (2005). Solution for the properties of a clustered network. Phys. Rev. E (3) 72 026136, 5. |
| [47] | Radin, C. and Sadun, L. (2013). Phase transitions in a complex network. J. Phys. A 46 305002. · Zbl 1314.82011 · doi:10.1088/1751-8113/46/30/305002 |
| [48] | Radin, C. and Yin, M. (2011). Phase transitions in exponential random graphs. Preprint. Available at . · Zbl 1278.05225 · doi:10.1214/12-AAP907 |
| [49] | Rinaldo, A., Fienberg, S. E. and Zhou, Y. (2009). On the geometry of discrete exponential families with application to exponential random graph models. Electron. J. Stat. 3 446-484. · Zbl 1326.62071 · doi:10.1214/08-EJS350 |
| [50] | Robbins, H. and Monro, S. (1951). A stochastic approximation method. Ann. Math. Statist. 22 400-407. · Zbl 0054.05901 · doi:10.1214/aoms/1177729586 |
| [51] | Sanov, I. N. (1961). On the probability of large deviations of random variables. In Select. Transl. Math. Statist. and Probability , Vol. 1 213-244. Amer. Math. Soc., Providence, RI. · Zbl 0112.10106 |
| [52] | Snijders, T. A. (2002). Markov chain Monte Carlo estimation of exponential random graph models. J. Soc. Structure 3 . |
| [53] | Snijders, T. A. B., Pattison, P. E., Robins, G. L. and Handcock, M. S. (2006). New specifications for exponential random graph models. Sociol. Method. 36 99-153. |
| [54] | Strauss, D. (1986). On a general class of models for interaction. SIAM Rev. 28 513-527. · Zbl 0612.60066 · doi:10.1137/1028156 |
| [55] | Talagrand, M. (2003). Spin Glasses : A Challenge for Mathematicians. Ergebnisse der Mathematik und Ihrer Grenzgebiete . 3. Folge. A Series of Modern Surveys in Mathematics [ Results in Mathematics and Related Areas . 3 rd Series. A Series of Modern Surveys in Mathematics ] 46 . Springer, Berlin. · Zbl 1033.82002 |
| [56] | Turán, P. (1941). Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 436-452. · Zbl 0026.26903 |
| [57] | Wasserman, S. and Faust, K. (2010). Social Network Analysis : Methods and Applications. Structural Analysis in the Social Sciences , 2nd ed. Cambridge Univ. Press, Cambridge. · Zbl 0926.91066 |
| [58] | Yin, M. (2012). Critical phenomena in exponential random graphs. Preprint. Available at . · Zbl 1285.82024 · doi:10.1007/s10955-013-0874-x |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
