Bayesian community detection. (English) Zbl 1407.62240

Summary: We introduce a Bayesian estimator of the underlying class structure in the stochastic block model, when the number of classes is known. The estimator is the posterior mode corresponding to a Dirichlet prior on the class proportions, a generalized Bernoulli prior on the class labels, and a beta prior on the edge probabilities. We show that this estimator is strongly consistent when the expected degree is at least of order \(\log^{2}{n}\), where \(n\) is the number of nodes in the network.


62H30 Classification and discrimination; cluster analysis (statistical aspects)
62G20 Asymptotic properties of nonparametric inference
62F15 Bayesian inference


Full Text: DOI arXiv Euclid


[1] Abbe, E., Bandeira, A. S., and Hall, G. (2014). “Exact Recovery in the Stochastic Block Model.” ArXiv:1405.3267v4. · Zbl 1359.94047
[2] Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2008). “Mixed Membership Stochastic Blockmodels.” Journal of Machine Learning Research, 9: 1981–2014. · Zbl 1225.68143
[3] Bickel, P. J. and Chen, A. (2009). “A Nonparametric View of Network Models and Newman-Girvan and Other Modularities.” Proceedings of the National Academy of Sciences of the United States of America, 106(50): 21068–21073. · Zbl 1359.62411
[4] Bickel, P. J., Chen, A., Zhao, Y., Levina, E., and Zhu, J. (2015). “Correction to the Proof of Consistency of Community Detection.” The Annals of Statistics, 43(1): 462–466. · Zbl 1310.62109
[5] Channarond, A., Daudin, J.-J., and Robin, S. (2012). “Classification and Estimation in the Stochastic Blockmodel Based on the Empirical Degrees.” Electronic Journal of Statistics, 6: 2574–2601. · Zbl 1295.62065
[6] Chen, K. and Lei, J. (2014). “Network Cross-Validation for Determining the Number of Communities in Network Data.” ArXiv:1411.1715v1.
[7] Chen, Y. and Xu, J. (2014). “Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices.” ArXiv:1402.1267v2.
[8] Côme, E. and Latouche, P. (2014). “Model Selection and Clustering in Stochastic Block Models with the Exact Integrated Complete Data Likelihood.” ArXiv:1303.2962.
[9] Csardi, G. and Nepusz, T. (2006). “The igraph Software Package for Complex Network Research.” InterJournal Complex Systems, 1695.
[10] Gao, C., Ma, Z., Zhang, A. Y., and Zhou, H. H. (2015). “Achieving Optimal Misclassification Proportion in Stochastic Block Model.” ArXiv:1505.03772v5. · Zbl 1440.62244
[11] Gao, C., Ma, Z., Zhang, A. Y., and Zhou, H. H. (2016). “Community Detection in Degree-Corrected Block Models.” ArXiv:1607.06993.
[12] Ghosal, S., Ghosh, J. K., and van der Vaart, A. W. (2000). “Convergence rates of posterior distributions.” The Annals of Statistics, 28(2): 500–531. · Zbl 1105.62315
[13] Glover, F. (1989). “Tabu Search – Part I.” ORSA Journal on Computing, 1(3): 190–206. · Zbl 0753.90054
[14] Hayashi, K., Konishi, T., and Kawamoto, T. (2016). “A Tractable Fully Bayesian Method for the Stochastic Block Model.” ArXiv:1602.02256v1.
[15] Hofman, J. M. and Wiggins, C. H. (2008). “Bayesian Approach to Network Modularity.” Physical Review Letters, 100: 258701.
[16] Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). “Stochastic Blockmodels: First Steps.” Social Networks, 5: 109–137.
[17] Jin, J. (2015). “Fast Community Detection by SCORE.” The Annals of Statistics, 43(1): 57–89. · Zbl 1310.62076
[18] Karrer, B. and Newman, M. E. J. (2011). “Stochastic Blockmodels and Community Structure in Networks.” Physical Review E, 83: 016107.
[19] Kpogbezan, G. B., van der Vaart, A. W., van Wieringen, W. N., Leday, G. G. R., and van de Wiel, M. A. (2016). “An empirical Bayes approach to network recovery using external knowledge.” ArXiv:1605.07514. · Zbl 1391.62226
[20] Lei, J. and Rinaldo, A. (2015). “Consistency of Spectral Clustering in Stochastic Block Models.” The Annals of Statistics, 43(1): 215–237. · Zbl 1308.62041
[21] McDaid, A. F., Brendan Murphy, T., Friel, N., and Hurley, N. J. (2013). “Improved Bayesian Inference for the Stochastic Block Model with Application to Large Networks.” Computational Statistics and Data Analysis, 60: 12–31. · Zbl 1365.62241
[22] Mossel, E., Neeman, J., and Sly, A. (2012). “Reconstruction and Estimation in the Planted Partition Model.” ArXiv:11202.1499v4. · Zbl 1320.05113
[23] Newman, M. and Girvan, M. (2004). “Finding and Evaluating Community Structure in Networks.” Physical Review E, 69: 026113.
[24] Nowicki, K. and Snijders, T. A. B. (2001). “Estimation and Prediction for Stochastic Blockstructures.” Journal of the American Statistical Association, 96(455): 1077–1087. · Zbl 1072.62542
[25] Park, Y. and Bader, J. S. (2012). “How Networks Change with Time.” Bioinformatics, 28(12): i40–i48.
[26] Pati, D. and Bhattacharya, A. (2015). “Optimal Bayesian Estimation in Stochastic Block Models.” ArXiv:1505.06794. · Zbl 1328.62178
[27] Robbins, H. (1955). “A Remark on Stirling’s Formula.” The American Mathematical Monthly, 62(1): 26–29. · Zbl 0068.05404
[28] Rohe, K., Chatterjee, S., and Yu, B. (2011). “Spectral Clustering and the High-Dimensional Stochastic Blockmodel.” The Annals of Statistics, 39(4): 1878–1915. · Zbl 1227.62042
[29] Saldana, D. F., Yu, Y., and Feng, Y. (2014). “How Many Communities Are There?” ArXiv:1412.1684v1.
[30] Sarkar, P. and Bickel, P. J. (2015). “Role of Normalization in Spectral Clustering for Stochastic Blockmodels.” The Annals of Statistics, 43(3): 962–990. · Zbl 1320.62150
[31] Snijders, T. A. 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
[32] Suwan, S., Lee, D. S., Tang, R., Sussman, D. L., Tang, M., and Priebe, C. E. (2016). “Empirical Bayes estimation for the stochastic blockmodel.” Electronic Journal of Statistics, 10: 761–782. · Zbl 1333.62088
[33] Wang, Y. X. R. and Bickel, P. J. (2015). “Likelihood-Based Model Selection for Stochastic Block Models.” ArXiv:1502.02069v1.
[34] Zachary, W. W. (1977). “An Information Flow Model for Conflict and Fission in Small Groups.” Journal of Anthropological Research, 33(4): 452–473.
[35] Zhang, A. Y. and Zhou, H. H. (2015). “Minimax Rates of Community Detection in Stochastic Block Models.” Preprint available at http://www.stat.yale.edu/ hz68/CommunityDetection.pdf. · Zbl 1355.60125
[36] Zhao, Y., Levina, E., and Zhu, J. (2012). “Consistency of Community Detection in Networks under Degree-Corrected Stochastic Block Models.” The Annals of Statistics, 40(4): 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. 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.