zbMATH — the first resource for mathematics

Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. (English) Zbl 1308.62131
Summary: Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In this paper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel and the degree-corrected stochastic blockmodel. We also show an analogous result for the more general random dot product graph model.

62H30 Classification and discrimination; cluster analysis (statistical aspects)
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI Euclid
[1] Athreya, A., Lyzinski, V., Marchette, D. J., Priebe, C. E., Sussman, D. L., and Tang, M., A limit theorem for scaled eigenvectors of random dot product graphs., Sankhya A , accepted for publication. · Zbl 1338.62061
[2] Bickel, P. J. and Chen, A., A nonparametric view of network models and Newman-Girvan and other modularities., Proc. Natl. Acad. Sci. USA , 106 :21068-21073, 2009. · Zbl 1359.62411
[3] Bickel, P. J., Chen, A., and Levina, E., The method of moments and degree distributions for network models., Ann. Statist. , 39:38-59, 2011. · Zbl 1232.91577
[4] Chaudhuri, K., Chung, F., and Tsiatas, A., Spectral partitioning of graphs with general degrees and the extended planted partition model. In, Proceedings of the 25th Conference on Learning Theory , 2012.
[5] Choi, D. S., Wolfe, P. J., and Airoldi, E. M., Stochastic blockmodels with a growing number of classes., Biometrika , 99:273-284, 2012. · Zbl 1318.62207
[6] Choi, D. and Wolfe, P. J., Co-clustering separately exchangeable network data., Ann. Statist. , 42(1):29-63, 2014. · Zbl 1294.62059
[7] Hoff, P. D., Raftery, A. E., and Handcock, M. S., Latent space approaches to social network analysis., J. Amer. Statist. Assoc. , 97(460) :1090-1098, 2002. · Zbl 1041.62098
[8] Holland, P. W., Laskey, K., and Leinhardt, S., Stochastic blockmodels: First steps., Social Networks , 5:109-137, 1983.
[9] Karrer, B. and Newman, M. E. J., Stochastic blockmodels and community structure in networks., Phys. Rev. E , 83, 2011.
[10] Lei, J. and Rinaldo, A., Consistency of spectral clustering in stochastic blockmodels., Ann. Statist. , 43:215-237, 2015. · Zbl 1308.62041
[11] Lyzinski, V., Sussman, D. L., Fishkind, D. E., Pao, H., Chen, L., Vogelstein, J. T., and Priebe, C. E., Spectral clustering for divide-and-conquer graph matching. Arxiv preprint at http://arxiv.org/abs/ 1310.1297, 2014.
[12] Mossel, E., Neeman, J., and Sly, A., Consistency thresholds for binary symmetric block models. ArXiv preprint at http://arxiv.org/abs/ 1407.1591, 2014. · Zbl 1336.05117
[13] Mossel, E., Neeman, J., and Sly, A., Stochastic block models and reconstruction., Probab. Theory Related Fields , · Zbl 1350.05154
[14] Newman, M. E. J., Modularity and community structure in networks., Proc. Natl. Acad. Sci. USA , 103(23) :8577-8582, 2006.
[15] Oliveira, R. I., Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges. Arxiv preprint at http://arxiv.org/abs /0911.0600, 2010.
[16] Pollard, D., Strong consistency of \(k\)-means clustering., Ann. Statist. , 9:135-140, 1981. · Zbl 0451.62048
[17] Qin, T. and Rohe, K., Regularized spectral clustering under the degree-corrected stochastic blockmodel., NIPS , 2013.
[18] Rohe, K., Chatterjee, S., and Yu, B., Spectral clustering and the high-dimensional stochastic blockmodel., Ann. Statist. , 39 :1878-1915, 2011. · Zbl 1227.62042
[19] Snijders, T. A. B. and Nowicki, K., Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure., J. Classification , 14:75-100, 1997. · Zbl 0896.62063
[20] Sussman, D. L., Tang, M., Fishkind, D. E., and Priebe, C. E., A consistent adjacency spectral embedding for stochastic blockmodel graphs., J. Amer. Statist. Assoc. , 107(499) :1119-1128, 2012. · Zbl 1443.62188
[21] Sussman, D. L., Tang, M., and Priebe, C. E., Consistent latent position estimation and vertex classification for random dot product graphs., IEEE Trans. Pattern. Anal. , 36:48-57, 2014.
[22] Suwan, S., Lee, D. S., Tang, R., Sussman, D. L., Tang, M., and Priebe, C. E., Empirical bayes estimation for the stochastic blockmodel. Arxiv preprint at arxiv.org/abs /1405.6070, 2014. · Zbl 1333.62088
[23] Tang, M., Sussman, D. L., and Priebe, C. E., Universally consistent vertex classification for latent position graphs., Ann. Statist. , 41 :1406-1430, 2013. · Zbl 1273.62147
[24] Tang, M., Athreya, A., Sussman, D. L., Lyzinski, V., and Priebe, C. E., A semiparametric two-sample hypothesis testing problem for random dot product graphs. ArXiv preprint at http://arxiv.org/abs/ 1403.7249, 2014. · Zbl 1308.62131
[25] Tropp, J. A., Freedman’s inequality for matrix martingales., Electron. Commun. Probab , 16:262-270, 2011. · Zbl 1225.60017
[26] Wolfe, P. J. and Olhede, S. C., Nonparametric graphon estimation. ArXiv preprint at http://arxiv.org/abs /1309/5936, 2013.
[27] Young, S. and Scheinerman, E., Random dot product graph models for social networks. In, Proceedings of the 5th International Conference on Algorithms and Models for the Web-Graph , pages 138-149, 2007. · Zbl 1136.05322
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.