×

Random graphs with a given degree sequence. (English) Zbl 1234.05206

Summary: Large graphs are sometimes studied through their degree sequences (power law or regular graphs). We study graphs that are uniformly chosen with a given degree sequence. Under mild conditions, it is shown that sequences of such graphs have graph limits in the sense of Lovász and Szegedy with identifiable limits. This allows simple determination of other features such as the number of triangles. The argument proceeds by studying a natural exponential model having the degree sequence as a sufficient statistic. The maximum likelihood estimate (MLE) of the parameters is shown to be unique and consistent with high probability. Thus \(n\) parameters can be consistently estimated based on a sample of size one. A fast, provably convergent, algorithm for the MLE is derived. These ingredients combine to prove the graph limit theorem. Along the way, a continuous version of the Erdős-Gallai characterization of degree sequences is derived.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C07 Vertex degrees
05A16 Asymptotic enumeration
05C30 Enumeration in graph theory
52B55 Computational aspects related to convexity
60F05 Central limit and other weak theorems
62F10 Point estimation
62F12 Asymptotic properties of parametric estimators
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[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] 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
[3] 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
[4] Barndorff-Nielsen, O. (1978). Information and Exponential Families in Statistical Theory . Wiley, Chichester. · Zbl 0387.62011
[5] Barvinok, A. (2010). What does a random contingency table look like? Combin. Probab. Comput. 19 517-539. · Zbl 1201.62075 · doi:10.1017/S0963548310000039
[6] Barvinok, A. (2010). On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries. Adv. Math. 224 316-339. · Zbl 1191.15031 · doi:10.1016/j.aim.2009.12.001
[7] Barvinok, A. and Hartigan, J. A. (2009). An asymptotic formula for the number of nonnegative integer matrices with prescibed row and column sums. Preprint. Available at . · Zbl 1269.05006
[8] Barvinok, A. and Hartigan, J. A. (2009). Maximum entropy Edgeworth estimates of volumes of polytopes. Preprint. Available at . · Zbl 1213.05015
[9] Barvinok, A. and Hartigan, J. A. (2010). Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes. Adv. in Appl. Math. 45 252-289. · Zbl 1213.05015 · doi:10.1016/j.aam.2010.01.004
[10] Barvinok, A. and Hartigan, J. A. (2010). The number of graphs and a random graph with a given degree sequence. Preprint. Available at . · Zbl 1213.05015 · doi:10.1016/j.aam.2010.01.004
[11] Bishop, Y. M. M., Fienberg, S. E. and Holland, P. W. (1975). Discrete Multivariate Analysis : Theory and Practice . MIT Press, Cambridge, MA. · Zbl 0332.62039
[12] Blitzstein, J. and Diaconis, P. (2009). A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Preprint. Available at . · Zbl 1238.60084
[13] Borgs, C., Chayes, J., Lovász, L., Sós, V. T. and Vesztergombi, K. (2006). Counting graph homomorphisms. In Topics in Discrete Mathematics. Algorithms Combin. 26 315-371. Springer, Berlin. · Zbl 1129.05050
[14] 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
[15] Borgs, C., Chayes, J., Lovász, L., Sós, V. T. and Vesztergombi, K. (2007). Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Preprint. Available at . · Zbl 1247.05124
[16] Brown, L. D. (1986). Fundamentals of Statistical Exponential Families with Applications in Statistical Decision Theory. Institute of Mathematical Statistics Lecture Notes-Monograph Series 9 . IMS, Hayward, CA. · Zbl 0685.62002
[17] Diaconis, P. and Freedman, D. (1984). Partial exchangeability and sufficiency. In Statistics : Applications and New Directions (Calcutta, 1981) 205-236. Indian Statist. Inst., Calcutta.
[18] Diaconis, P., Holmes, S. and Janson, S. (2008). Threshold graph limits and random threshold graphs. Internet Math. 5 267-320 (2009). · Zbl 1184.68356 · doi:10.1080/15427951.2008.10129166
[19] Diaconis, P. and Janson, S. (2008). Graph limits and exchangeable random graphs. Rend. Mat. Appl. (7) 28 33-61. · Zbl 1162.60009
[20] Diaconis, P. and Ylvisaker, D. (1979). Conjugate priors for exponential families. Ann. Statist. 7 269-281. · Zbl 0405.62011 · doi:10.1214/aos/1176344611
[21] Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 17-61. · Zbl 0103.16301
[22] Erdős, P. and Gallai, T. (1960). Graphen mit punkten vorgeschriebenen grades. Mat. Lapok 11 264-274. · Zbl 0103.39701
[23] Gale, D. (1957). A theorem on flows in networks. Pacific J. Math. 7 1073-1082. · Zbl 0087.16303 · doi:10.2140/pjm.1957.7.1073
[24] Gutiérrez-Peña, E. and Smith, A. F. M. (1995). Conjugate parameterizations for natural exponential families. J. Amer. Statist. Assoc. 90 1347-1356. · Zbl 0868.62029 · doi:10.2307/2291525
[25] Gutiérrez-Peña, E. and Smith, A. F. M. (1996). Erratum: “Conjugate parameterizations for natural exponential families.” J. Amer. Statist. Assoc. 91 1757. · Zbl 0868.62029
[26] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13-30. · Zbl 0127.10602 · doi:10.2307/2282952
[27] 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
[28] 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
[29] Hunter, D. R. (2004). MM algorithms for generalized Bradley-Terry models. Ann. Statist. 32 384-406. · Zbl 1105.62359 · doi:10.1214/aos/1079120141
[30] Jackson, M. O. (2008). Social and Economic Networks . Princeton Univ. Press, Princeton, NJ. · Zbl 1149.91051
[31] Kolaczyk, E. D. (2009). Statistical Analysis of Network Data : Methods and Models . Springer, New York. · Zbl 1277.62021
[32] Lauritzen, S. L. (1988). Extremal Families and Systems of Sufficient Statistics. Lecture Notes in Statistics 49 . Springer, New York. · Zbl 0681.62009
[33] Li, L., Alderson, D., Doyle, J. C. and Willinger, W. (2005). Towards a theory of scale-free graphs: Definition, properties, and implications. Internet Math. 2 431-523. · Zbl 1103.05082 · doi:10.1080/15427951.2005.10129111
[34] 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
[35] Mahadev, N. V. R. and Peled, U. N. (1995). Threshold Graphs and Related Topics. Annals of Discrete Mathematics 56 . North-Holland, Amsterdam. · Zbl 0852.05001
[36] McDiarmid, C. (1989). On the method of bounded differences. In Surveys in Combinatorics, 1989 (Norwich, 1989) (J. Siemons, ed.). London Mathematical Society Lecture Note Series 141 148-188. Cambridge Univ. Press, Cambridge. · Zbl 0712.05012
[37] McKay, B. D. (2010). Subgraphs of dense random graphs with specified degrees. Preprint. Available at . · Zbl 1226.05228 · doi:10.1017/S0963548311000034
[38] McKay, B. D. and Wormald, N. C. (1990). Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin. 11 565-580. · Zbl 0739.05043 · doi:10.1016/S0195-6698(13)80042-X
[39] Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6 161-179. · Zbl 0823.05050 · doi:10.1002/rsa.3240060204
[40] Molloy, M. and Reed, B. (1998). The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput. 7 295-305. · Zbl 0916.05064 · doi:10.1017/S0963548398003526
[41] Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45 167-256 (electronic). · Zbl 1029.68010 · doi:10.1137/S003614450342480
[42] Newman, M. E. J., Barabasi, A.-L. and Watts, D. J. (eds.) (2006). The Structure and Dynamics of Networks. Princeton Studies in Complexity . Princeton Univ. Press, Princeton, NJ.
[43] Park, J. and Newman, M. E. J. (2004). Statistical mechanics of networks. Phys. Rev. E (3) 70 066117, 13.
[44] Portnoy, S. (1984). Asymptotic behavior of M -estimators of p regression parameters when p 2 / n is large. I. Consistency. Ann. Statist. 12 1298-1309. · Zbl 0584.62050 · doi:10.1214/aos/1176346793
[45] Portnoy, S. (1985). Asymptotic behavior of M estimators of p regression parameters when p 2 / n is large. II. Normal approximation. Ann. Statist. 13 1403-1417. · Zbl 0601.62026 · doi:10.1214/aos/1176349744
[46] Portnoy, S. (1988). Asymptotic behavior of likelihood methods for exponential families when the number of parameters tends to infinity. Ann. Statist. 16 356-366. · Zbl 0637.62026 · doi:10.1214/aos/1176350710
[47] Portnoy, S. (1991). Correction: “Asymptotic behavior of M estimators of p regression parameters when p 2 / n is large. II. Normal approximation.” Ann. Statist. 19 2282. · Zbl 0745.62017 · doi:10.1214/aos/1176348403
[48] Robins, G., Snijders, T., Wang, P., Handcock, M. and Pattison, P. (2007). Recent developments in exponential random graph ( p \ast ) models for social networks. Social Networks 29 192-215.
[49] Ryser, H. J. (1957). Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9 371-377. · Zbl 0079.01102 · doi:10.4153/CJM-1957-044-3
[50] Simons, G. and Yao, Y.-C. (1999). Asymptotics when the number of parameters tends to infinity in the Bradley-Terry model for paired comparisons. Ann. Statist. 27 1041-1060. · Zbl 0951.62061 · doi:10.1214/aos/1018031267
[51] Tsourakakis, C. (2008). Fast counting of triangles in large real networks: Algorithms and laws. In Proc. of ICDM 2008 608-617. IEEE Computer Society, Los Alamitos, CA.
[52] Wainwright, M. J. and Jordan, M. I. (2008). Graphical models, exponential families and variational inference. Foundations and Trends in Machine Learning 1 1-305. · Zbl 1193.62107 · doi:10.1561/2200000001
[53] Willinger, W., Alderson, D. and Doyle, J. C. (2009). Mathematics and the Internet: A source of enormous confusion and great potential. Notices Amer. Math. Soc. 56 586-599. · Zbl 1168.90004
[54] Wormald, N. C. (1999). Models of random regular graphs. In Surveys in Combinatorics , 1999 ( Canterbury ). London Mathematical Society Lecture Note Series 267 239-298. Cambridge Univ. Press, Cambridge. · Zbl 0935.05080
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.