×

The method of moments and degree distributions for network models. (English) Zbl 1232.91577

Summary: Probability models on graphs are becoming increasingly important in many applications, but statistical tools for fitting such models are not yet well developed. Here we propose a general method of moments approach that can be used to fit a large class of probability models through empirical counts of certain patterns in a graph. We establish some general asymptotic properties of empirical graph moments and prove consistency of the estimates as the graph size grows for all ranges of the average degree including \(\Omega (1)\). Additional results are obtained for the important special case of degree distributions.

MSC:

91D30 Social networks; opinion dynamics
62E10 Characterization and structure theory of statistical distributions
62G05 Nonparametric estimation
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] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[3] Bickel, P. J. and Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106 21068-21073. · Zbl 1359.62411
[4] Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3-122. · Zbl 1123.05083 · doi:10.1002/rsa.20168
[5] Chartrand, G., Lesniak, L. and Behzad, M. (1986). Graphs and Digraphs , 2nd ed. Wadsworth and Brooks, Monterey, CA. · Zbl 0666.05001
[6] Chatterjee, S. and Diaconis, P. (2011). Estimating and understanding exponential random graph models. Unpublished manuscript. Available at . · Zbl 1293.62046
[7] Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Comb. 6 125-145. · Zbl 1009.05124 · doi:10.1007/PL00012580
[8] de Solla Price, D. J. (1965). Networks of scientific papers. Science 149 510-515.
[9] Decelle, A., Krzakala, F., Moore, C. and Zdeborová, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Available at . · Zbl 1228.90101 · doi:10.1137/090750755
[10] Diaconis, P. and Janson, S. (2008). Graph limits and exchangeable random graphs. Rend. Mat. Appl. (7) 28 33-61. · Zbl 1162.60009
[11] Doukhan, P. (1994). Mixing: Properties and Examples. Lecture Notes in Statistics 85 . Springer, New York. · Zbl 0801.60027
[12] Feller, W. (1971). An Introduction to Probability Theory and Its Applications. Vol. II , 2nd ed. Wiley, New York. · Zbl 0219.60003
[13] Frank, O. and Strauss, D. (1986). Markov graphs. J. Amer. Statist. Assoc. 81 832-842. · Zbl 0607.05057 · doi:10.2307/2289017
[14] Handcock, M. (2003). Assessing degeneracy in statistical models of social networks. Working Paper 39, Center for Statistics and the Social Sciences.
[15] Handcock, M. S., Raftery, A. E. and Tantrum, J. M. (2007). Model-based clustering for social networks. J. Roy. Statist. Soc. Ser. A 170 301-354. · Zbl 05273954 · doi:10.1111/j.1467-985X.2007.00471.x
[16] Hoff, P. D. (2007). Modeling homophily and stochastic equivalence in symmetric relational data. In Advances in Neural Information Processing Systems 19 . MIT Press, Cambridge, MA.
[17] Hoff, P. D., Raftery, A. E. and Handcock, M. S. (2002). Latent space approaches to social network analysis. J. Amer. Statist. Assoc. 97 1090-1098. · Zbl 1041.62098 · doi:10.1198/016214502388618906
[18] Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks 5 109-137. · doi:10.1016/0378-8733(83)90021-7
[19] 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
[20] Hoover, D. (1979). Relations on probability spaces and arrays of random variables. Technical report, Institute for Advanced Study, Princeton, NJ.
[21] Kallenberg, O. (2005). Probabilistic Symmetries and Invariance Principles . Springer, New York. · Zbl 1084.60003 · doi:10.1007/0-387-28861-9
[22] Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Phys. Rev. E (3) 83 016107. · doi:10.1103/PhysRevE.83.016107
[23] Newman, M. E. J. (2006). Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E (3) 74 036104. · doi:10.1103/PhysRevE.74.036104
[24] Newman, M. E. J. (2010). Networks: An Introduction . Oxford Univ. Press, Oxford. · Zbl 1195.94003
[25] Nowicki, K. and Snijders, T. A. B. (2001). Estimation and prediction for stochastic blockstructures. J. Amer. Statist. Assoc. 96 1077-1087. · Zbl 1072.62542 · doi:10.1198/016214501753208735
[26] Picard, F., Daudin, J. J., Koskas, M., Schbath, S. and Robin, S. (2008). Assessing the exceptionality of network motifs. J. Comput. Biol. 15 1-20. · doi:10.1089/cmb.2007.0137
[27] Robins, G., Snijders, T., Wang, P., Handcock, M. and Pattison, P. (2007). Recent developments in exponential random graphs models ( p \ast ) for social networks. Social Networks 29 192-215.
[28] Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic block model. Ann. Statist. · Zbl 1227.62042
[29] Serfling, R. J. (1980). Approximation Theorems of Mathematical Statistics . Wiley, New York. · Zbl 0538.62002
[30] Shalizi, C. R. and Rinaldo, A. (2011). Projective structure and parametric inference in exponential families. Carnegie Mellon Univ. Unpublished manuscript.
[31] Snijders, T. A. B. and Nowicki, K. (1997). Estimation and prediction for stochastic blockmodels for graphs with latent block structure. J. Classification 14 75-100. · Zbl 0896.62063 · doi:10.1007/s003579900004
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.