Consistency of maximum-likelihood and variational estimators in the stochastic block model. (English) Zbl 1295.62028

Summary: The stochastic block model (SBM) is a probabilistic model designed to describe heterogeneous directed and undirected graphs. In this paper, we address the asymptotic inference in SBM by use of maximum-likelihood and variational approaches. The identifiability of SBM is proved while asymptotic properties of maximum-likelihood and variational estimators are derived. In particular, the consistency of these estimators is settled for the probability of an edge between two vertices (and for the group proportions at the price of an additional assumption), which is to the best of our knowledge the first result of this type for variational estimators in random graphs.


62G05 Nonparametric estimation
62G20 Asymptotic properties of nonparametric inference
62E17 Approximations to statistical distributions (nonasymptotic)
62H30 Classification and discrimination; cluster analysis (statistical aspects)
05C80 Random graphs (graph-theoretic aspects)


Mixnet; StOCNET
Full Text: DOI arXiv Euclid


[1] Allman, E., Matias, C., and Rhodes, J. (2009). Identifiability of parameters in latent structure models with many observed variables., Annals of Statistics , 37 , 3099-3132. · Zbl 1191.62003
[2] Allman, E., Matias, C., and Rhodes, J. A. (2011). Parameter identifiability in a class of random graph mixture models., Journal of Statistical Planning and Inference , 141 (5), 1719-1736. · Zbl 1207.62010
[3] Ambroise, C. and Matias, C. (2012). New consistent and asymptotically normal estimators for random graph mixture models., JRSS. B , 74 (1), 3-35.
[4] Andrieu, C. and AtchadĂ©, Y. F. (2007). On the efficiency of adaptive mcmc algorithms., Elec. Comm. in Probab. , 12 , 336-349. · Zbl 1129.65006
[5] Bickel, P. and Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities., PNAS , pages 1-6. · Zbl 1359.62411
[6] Bickel, P. J., Chen, A., and Levina, E. (2011). The method of moments and degree distributions for network models., Ann. Statist. , 39 (5), 2280-2301. · Zbl 1232.91577
[7] Boer, P., Huisman, M., Snijders, T., Steglich, C., Wichers, L., and Zeggelink, E. (2006). Stocnet: an open software system for the advanced statistical analysis of social networks, version 1.7. groningen:, Ics/scienceplus.
[8] Choi, D. S., Wolfe, P. J., and Airoldi, E. M. (2012). Stochastic blockmodels with growing number of classes., Biometrika , · Zbl 1318.62207
[9] Daudin, J.-J., Picard, F., and Robin, S. (2008). A mixture model for random graphs., Stat Comput , 18 , 173-183.
[10] Gazal, S., Daudin, J.-J., and Robin, S. (2011). Accuracy of variational estimates for random graph mixture models., J. Comput. Simul. · Zbl 1431.62232
[11] Holland, P., Laskey, K., and Leinhardt, S. (1983). Stochastic blockmodels: Some first steps., Social Networks , 5 , 109-137.
[12] Jordan, M. I., Ghahramni, Z., Jaakkola, T. S., and Saul, L. K. (1999). An introduction to variational methods for graphical models., Machine Learning , 37 , 183-233. · Zbl 1033.68081
[13] Mariadassou, M., Robin, S., and Vacher, C. (2010). Uncovering latent structure in valued graphs: A variational approach., Ann. Appl. Stat. , 4 , 715-742. · Zbl 1194.62125
[14] Massart, P. (2007)., Concentration Inequalities and Model Selection , volume 1896 of Lecture Notes in Mathematics . Springer, Berlin. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6-23, 2003, With a foreword by Jean Picard. · Zbl 1170.60006
[15] Mixnet (2009)., .
[16] Nowicki, K. and Snijders, T. (2001). Estimation and prediction for stochastic block-structures., J. Am. Stat. Assoc. , 96 , 1077-1087. · Zbl 1072.62542
[17] Picard, F., Miele, V., Daudin, J.-J., Cottret, L., and Robin, S. (2009). Deciphering the connectivity structure of biological networks using mixnet., BMC Bioinformatics , 10 .
[18] Rohe, K., Chatterjee, S., and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel., Ann. Statist. , 39 (4), 1878-1915. · Zbl 1227.62042
[19] Snijders, T. A. B. and Nowicki, K. (1997). Estimation and prediction for stochastic blockmodels for graphs with latent block structure., Journal of Classification , 14 , 75-100. · Zbl 0896.62063
[20] van der Vaart, A. W. and Wellner, J. A. (1996)., Weak Convergence and Empirical Processes With Applications to Statistics . Springer Series in Statistics. · Zbl 0862.60002
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.