Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. (English) Zbl 1292.62042

Summary: Variational methods for parameter estimation are an active research area, potentially offering computationally tractable heuristics with theoretical performance bounds. We build on recent work that applies such methods to network data, and establish asymptotic normality rates for parameter estimates of stochastic blockmodel data, by either maximum likelihood or variational estimation. The result also applies to various sub-models of the stochastic blockmodel found in the literature.


62F12 Asymptotic properties of parametric estimators
Full Text: DOI arXiv Euclid


[1] 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
[2] Bickel, P. J., Chen, A. and Levina, E. (2011). The method of moments and degree distributions for network models. Ann. Statist. 39 2280-2301. · Zbl 1232.91577
[3] 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
[4] Celisse, A., Daudin, J. J. and Pierre, L. (2011). Consistency of maximum-likelihood and variational estimators in the stochastic block model. Available at . 1105.3288 · Zbl 1295.62028
[5] Channarond, A., Daudin, J. J. and Robin, S. (2011). Classification and estimation in the stochastic block model based on the empirical degrees. Available at . 1110.6517 · Zbl 1295.62065
[6] Chatterjee, S. (2012). Matrix estimation by universal singular value thresholding. Preprint. Available at . 1212.1247 · Zbl 1308.62038
[7] Chaudhuri, K., Chung, F. and Tsiatas, A. (2012). Spectral clustering of graphs with general degrees in the extended planted partition model. J. Mach. Learn. Res. 23 1-23.
[8] Choi, D. S., Wolfe, P. J. and Airoldi, E. M. (2012). Stochastic blockmodels with a growing number of classes. Biometrika 99 273-284. · Zbl 1318.62207
[9] Coja-Oghlan, A. and Lanka, A. (2008). Partitioning random graphs with general degree distributions. In Fifth IFIP International Conference on Theoretical Computer Science-TCS 2008. IFIP Int. Fed. Inf. Process. 273 127-141. Springer, New York.
[10] Daudin, J. J., Picard, F. and Robin, S. (2008). A mixture model for random graphs. Stat. Comput. 18 173-183.
[11] 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
[12] 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
[13] Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Phys. Rev. E (3) 83 016107, 10.
[14] Latouche, P., Birmelé, E. and Ambroise, C. (2011). Overlapping stochastic block models with application to the French political blogosphere. Ann. Appl. Stat. 5 309-336. · Zbl 1220.62083
[15] Lazer, D., Pentland, A. S., Adamic, L., Aral, S., Barabasi, A. L., Brewer, D., Christakis, N., Contractor, N., Fowler, J., Gutmann, M. et al. (2009). Life in the network: The coming age of computational social science. Science 323 721-723.
[16] Le Cam, L. and Yang, G. L. (1988). On the preservation of local asymptotic normality under information loss. Ann. Statist. 16 483-520. · Zbl 0661.62016
[17] Lehmann, E. L. and Romano, J. P. (2005). Testing Statistical Hypotheses , 3rd ed. Springer, New York. · Zbl 1076.62018
[18] Proulx, S. R., Promislow, D. E. L. and Phillips, P. C. (2005). Network thinking in ecology and evolution. Trends in Ecology & Evolution 20 345-353.
[19] Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Statist. 39 1878-1915. · Zbl 1227.62042
[20] Rohe, K., Qin, T. and Fan, H. (2012). The highest dimensional stochastic blockmodel with a regularized estimator. Preprint. Available at . 1206.2380 · Zbl 1482.62063
[21] 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
[22] Van der Vaart, A. W. (2000). Asymptotic Statistics 3 . Cambridge Univ. Press, Cambridge. · Zbl 0910.62001
[23] Zhao, Y., Levina, E. and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Statist. 40 2266-2292. · Zbl 1257.62095
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.