The Annals of Statistics
- Ann. Statist.
- Volume 39, Number 5 (2011), 2280-2301.
The method of moments and degree distributions for network models
Peter J. Bickel, Aiyou Chen, and Elizaveta Levina
Full-text: Open access
Abstract
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 Ω(1). Additional results are obtained for the important special case of degree distributions.
Article information
Source
Ann. Statist. Volume 39, Number 5 (2011), 2280-2301.
Dates
First available in Project Euclid: 11 November 2011
Permanent link to this document
http://projecteuclid.org/euclid.aos/1321020525
Digital Object Identifier
doi:10.1214/11-AOS904
Mathematical Reviews number (MathSciNet)
MR2906868
Zentralblatt MATH identifier
06008036
Subjects
Primary: 62E10: Characterization and structure theory
Secondary: 62G05: Estimation
Keywords
Social networks block model community detection
Citation
Bickel, Peter J.; Chen, Aiyou; Levina, Elizaveta. The method of moments and degree distributions for network models. Ann. Statist. 39 (2011), no. 5, 2280--2301. doi:10.1214/11-AOS904. http://projecteuclid.org/euclid.aos/1321020525.
References
- Aldous, D. J. (1981). Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11 581–598.Mathematical Reviews (MathSciNet): MR637937
Zentralblatt MATH: 0474.60044
Digital Object Identifier: doi: 10.1016/0047-259X(81)90099-3 - Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509–512.Mathematical Reviews (MathSciNet): MR2091634
Digital Object Identifier: doi: 10.1126/science.286.5439.509 - 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.
- Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3–122.Mathematical Reviews (MathSciNet): MR2337396
- Chartrand, G., Lesniak, L. and Behzad, M. (1986). Graphs and Digraphs, 2nd ed. Wadsworth and Brooks, Monterey, CA.
- Chatterjee, S. and Diaconis, P. (2011). Estimating and understanding exponential random graph models. Unpublished manuscript. Available at arXiv:1102.2650.
- Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Comb. 6 125–145.Mathematical Reviews (MathSciNet): MR1955514
Zentralblatt MATH: 1009.05124
Digital Object Identifier: doi: 10.1007/PL00012580 - de Solla Price, D. J. (1965). Networks of scientific papers. Science 149 510–515.
- 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 arXiv:1109.3041.
- Diaconis, P. and Janson, S. (2008). Graph limits and exchangeable random graphs. Rend. Mat. Appl. (7) 28 33–61.
- Doukhan, P. (1994). Mixing: Properties and Examples. Lecture Notes in Statistics 85. Springer, New York.Mathematical Reviews (MathSciNet): MR1312160
- Feller, W. (1971). An Introduction to Probability Theory and Its Applications. Vol. II, 2nd ed. Wiley, New York.Mathematical Reviews (MathSciNet): MR270403
- Frank, O. and Strauss, D. (1986). Markov graphs. J. Amer. Statist. Assoc. 81 832–842.Mathematical Reviews (MathSciNet): MR860518
Zentralblatt MATH: 0607.05057
Digital Object Identifier: doi: 10.2307/2289017 - Handcock, M. (2003). Assessing degeneracy in statistical models of social networks. Working Paper 39, Center for Statistics and the Social Sciences.
- 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.Mathematical Reviews (MathSciNet): MR2364300
Digital Object Identifier: doi: 10.1111/j.1467-985X.2007.00471.x - 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.
- 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.Mathematical Reviews (MathSciNet): MR1951262
Zentralblatt MATH: 1041.62098
Digital Object Identifier: doi: 10.1198/016214502388618906 - Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks 5 109–137.Mathematical Reviews (MathSciNet): MR718088
Digital Object Identifier: doi: 10.1016/0378-8733(83)90021-7 - Holland, P. W. and Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76 33–65.Mathematical Reviews (MathSciNet): MR608176
Zentralblatt MATH: 0457.62090
Digital Object Identifier: doi: 10.2307/2287037 - Hoover, D. (1979). Relations on probability spaces and arrays of random variables. Technical report, Institute for Advanced Study, Princeton, NJ.
- Kallenberg, O. (2005). Probabilistic Symmetries and Invariance Principles. Springer, New York.
- Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Phys. Rev. E (3) 83 016107.Mathematical Reviews (MathSciNet): MR2788206
Digital Object Identifier: doi: 10.1103/PhysRevE.83.016107 - Newman, M. E. J. (2006). Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E (3) 74 036104.Mathematical Reviews (MathSciNet): MR2282139
Digital Object Identifier: doi: 10.1103/PhysRevE.74.036104 - Newman, M. E. J. (2010). Networks: An Introduction. Oxford Univ. Press, Oxford.Mathematical Reviews (MathSciNet): MR2676073
- Nowicki, K. and Snijders, T. A. B. (2001). Estimation and prediction for stochastic blockstructures. J. Amer. Statist. Assoc. 96 1077–1087.Mathematical Reviews (MathSciNet): MR1947255
Zentralblatt MATH: 1072.62542
Digital Object Identifier: doi: 10.1198/016214501753208735 - 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.
- Robins, G., Snijders, T., Wang, P., Handcock, M. and Pattison, P. (2007). Recent developments in exponential random graphs models (p∗) for social networks. Social Networks 29 192–215.
- Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic block model. Ann. Statist. To appear.
- Serfling, R. J. (1980). Approximation Theorems of Mathematical Statistics. Wiley, New York.Mathematical Reviews (MathSciNet): MR595165
- Shalizi, C. R. and Rinaldo, A. (2011). Projective structure and parametric inference in exponential families. Carnegie Mellon Univ. Unpublished manuscript.
- 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.Mathematical Reviews (MathSciNet): MR1449742
Zentralblatt MATH: 0896.62063
Digital Object Identifier: doi: 10.1007/s003579900004
- You have access to this content.
- You have partial access to this content.
- You do not have access to this content.
More like this
- Introduction: How to Deal with Uncertainty in Population Forecasting?
Lutz1, Wolfgang and Goldstein, Joshua R., International Statistical Review, 2004 - Exchangeable Random Networks
Bassetti,, F., Lagomarsino, M. Cosentino, and Mandrà, S., Internet Mathematics, 2007 - Model Selection for Social Networks Using Graphlets
Janssen, Jeannette, Hurshman, Matt, and Kalyaniwalla, Nauzer, Internet Mathematics, 2012
- Introduction: How to Deal with Uncertainty in Population Forecasting?
Lutz1, Wolfgang and Goldstein, Joshua R., International Statistical Review, 2004 - Exchangeable Random Networks
Bassetti,, F., Lagomarsino, M. Cosentino, and Mandrà, S., Internet Mathematics, 2007 - Model Selection for Social Networks Using Graphlets
Janssen, Jeannette, Hurshman, Matt, and Kalyaniwalla, Nauzer, Internet Mathematics, 2012 - A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
Blitzstein, Joseph and Diaconis, Persi, Internet Mathematics, 2010 - A new multivariate measurement error model with
zero-inflated dietary data, and its application to dietary
assessment
Zhang, Saijuan, Carroll, Raymond J., Midthune, Douglas, Guenther, Patricia M., Krebs-Smith, Susan M., Kipnis, Victor, Dodd, Kevin W., Buckman, Dennis W., Tooze, Janet A., and Freedman, Laurence, The Annals of Applied Statistics, 2011 - Recovery and Resource Allocation Strategies to Maximize Mobile Network Survivability by Using Game Theories and Optimization Techniques
Chen, Pei-Yu and Lin, Frank Yeong-Sung, Journal of Applied Mathematics, 2013 - Connectivity and equilibrium in random games
Daskalakis, Constantinos, Dimakis, Alexandros G., and Mossel, Elchanan, The Annals of Applied Probability, 2011 - Bootstrap inference for network construction with an application to a breast cancer microarray study
Li, Shuang, Hsu, Li, Peng, Jie, and Wang, Pei, The Annals of Applied Statistics, 2013 - On the estimation of extreme tail probabilities
Hall, Peter and Weissman, Ishay, The Annals of Statistics, 1997 - Large cliques in a power-law random graph
Janson, Svante, Łuczak, Tomasz, and Norros, Ilkka, Journal of Applied Probability, 2010