Network Cross-Validation for Determining the Number of Communities in Network Data

References

• Abbe, E., Bandeira, A. S., and Hall, G. (2016), “Exact Recovery in the Stochastic Block Model,” IEEE Transactions on Information Theory, 62, 471–487.
   Web of Science ®Google Scholar
• Adamic, L. A., and Glance, N. (2005), “The Political Blogosphere and the 2004 US Election: Divided They Blog,” in Proceedings of the 3rd International Workshop on Link Discovery, ACM, 36–43.
   Google Scholar
• Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2008), “Mixed Membership Stochastic Blockmodels,” The Journal of Machine Learning Research, 9, 1981–2014.
   PubMed Web of Science ®Google Scholar
• Amini, A. A., Chen, A., Bickel, P. J., and Levina, E. (2013), “Pseudo-Likelihood Methods for Community Detection in Large Sparse Networks,” The Annals of Statistics, 41, 2097–2122.
   Web of Science ®Google Scholar
• Anandkumar, A., Ge, R., Hsu, D., and Kakade, S. M. (2014), “A Tensor Approach to Learning Mixed Membership Community Models,” Journal of Machine Learning Research, 15, 2239–2312.
   Web of Science ®Google Scholar
• 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, 106, 21068–21073.
   PubMed Web of Science ®Google Scholar
• Bickel, P. J., and Sarkar, P. (2016), “Hypothesis Testing for Automated Community Detection in Networks,” Journal of the Royal Statistical Society, Series B, 78, 253–273.
   Google Scholar
• Borgs, C., Chayes, J., and Smith, A. (2015), “Private Graphon Estimation for Sparse Graphs,” in Advances in Neural Information Processing Systems, pp. 1369–1377.
   Google Scholar
• Charikar, M., Guha, S., Tardos, É., and Shmoys, D. B. (1999), “A Constant-Factor Approximation Algorithm for the k-Median Problem,” in Proceedings of the Thirty-First Annual ACM Symposium on Theory of computing, ACM, 1–10.
   Google Scholar
• Chatterjee, S. (2014), “Matrix Estimation by Universal Singular Value Thresholding,” The Annals of Statistics, 43, 177–214.
   Web of Science ®Google Scholar
• Chaudhuri, K., Chung, F., and Tsiatas, A. (2012), “Spectral Clustering of Graphs With General Degrees in the Extended Planted Partition Model,” JMLR: Workshop and Conference Proceedings, pp. 35.1–35.23.
   Google Scholar
• Chen, Y., Sanghavi, S., and Xu, H. (2012), “Clustering Sparse Graphs,” in Advances in Neural Information Processing Systems 25, pp. 2213–2221.
   Google Scholar
• Daudin, J.-J., Picard, F., and Robin, S. (2008), “A Mixture Model for Random Graphs,” Statistics and Computing, 18, 173–183.
   Web of Science ®Google Scholar
• Decelle, A., Krzakala, F., Moore, C., and Zdeborová, L. (2011), “Asymptotic Analysis of the Stochastic Block Model for Modular Networks and Its Algorithmic Applications,” Physical Review E, 84, 066106-1–066106-19.
   Web of Science ®Google Scholar
• Faust, K., and Wasserman, S. (1992), “Blockmodels: Interpretation and Evaluation,” Social Networks, 14, 5–61.
   Web of Science ®Google Scholar
• Fishkind, D. E., Sussman, D. L., Tang, M., Vogelstein, J. T., and Priebe, C. E. (2013), “Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters are Unknown,” SIAM Journal on Matrix Analysis and Applications, 34, 23–39.
   Web of Science ®Google Scholar
• Gao, C., Lu, Y., and Zhou, H. H. (2015), “Rate-Optimal Graphon Estimation,” The Annals of Statistics, 43, 2624–2652.
   Web of Science ®Google Scholar
• Handcock, M. S., Raftery, A. E., and Tantrum, J. M. (2007), “Model-Based Clustering for Social Networks,” Journal of the Royal Statistical Society, Series A, 170, 301–354.
   Google Scholar
• Hoff, P. (2008), “Modeling Homophily and Stochastic Equivalence in Symmetric Relational Data,” in Advances in Neural Information Processing Systems, pp. 657–664.
   Google Scholar
• Hoff, P. D., Raftery, A. E., and Handcock, M. S. (2002), “Latent Space Approaches to Social Network Analysis,” Journal of the American Statistical Association, 97, 1090–1098.
   Web of Science ®Google Scholar
• Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983), “Stochastic Blockmodels: First Steps,” Social Networks, 5, 109–137.
   Web of Science ®Google Scholar
• Jin, J. (2015), “Fast Community Detection by SCORE,” The Annals of Statistics, 43, 57–89.
   Web of Science ®Google Scholar
• Josse, J., and Husson, F. (2012), “Selecting the Number of Components in Principal Component Analysis Using Cross-Validation Approximations,” Computational Statistics & Data Analysis, 56, 1869– 1879.
   Web of Science ®Google Scholar
• Karrer, B., and Newman, M. E. (2011), “Stochastic Blockmodels and Community Structure in Networks,” Physical Review E, 83, 016107-1–016107-10.
   Web of Science ®Google Scholar
• Kemp, C., Tenenbaum, J. B., Griffiths, T. L., Yamada, T., and Ueda, N. (2006), “Learning Systems of Concepts With an Infinite Relational Model,” in AAAI (Vol. 3), p. 5.
   Google Scholar
• Krebs, V. (2004), “Social Network Analysis Software & Services for Organizations, Communities, and Their Consultants,” available at http://www.orgnet.com/
   Google Scholar
• Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., and Zhang, P. (2013), “Spectral Redemption in Clustering Sparse Networks,” Proceedings of the National Academy of Sciences, 110, 20935–20940.
   PubMed Web of Science ®Google Scholar
• Latouche, P., Birmele, E., and Ambroise, C. (2012), “Variational Bayesian Inference and Complexity Control for Stochastic Block Models,” Statistical Modelling, 12, 93–115.
   Web of Science ®Google Scholar
• Lei, J. (2016), “A Goodness-of-Fit Test for Stochastic Block Models,” The Annals of Statistics, 44, 401–424.
   Web of Science ®Google Scholar
• Lei, J., and Rinaldo, A. (2015), “Consistency of Spectral Clustering in Stochastic Block Models,” The Annals of Statistics, 43, 215–237.
   Web of Science ®Google Scholar
• Lei, J., and Zhu, L. (2014), “A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models,” Statistica Sinica, 27.
   Google Scholar
• Li, S., and Svensson, O. (2013), “Approximating k-Median via Pseudo-Approximation,” in Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, ACM, pp. 901–910.
   Google Scholar
• Massoulié, L. (2014), “Community Detection Thresholds and the Weak Ramanujan Property,” in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, pp. 694–703.
   Google Scholar
• McDaid, A. F., Murphy, T. B., Friel, N., and Hurley, N. J. (2013), “Improved Bayesian inference for the stochastic Block Model With Application to Large Networks,” Computational Statistics & Data Analysis, 60, 12–31.
   Web of Science ®Google Scholar
• McSherry, F. (2001), “Spectral Partitioning of Random Graphs,” in 42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings, IEEE, 529–537.
   Google Scholar
• Mossel, E., Neeman, J., and Sly, A. (2013), “A Proof Of The Block Model Threshold Conjecture,” arXiv preprint:1311.4115.
   Google Scholar
• Newman, M. E. (2006), “Modularity and Community Structure in Networks,” Proceedings of the National Academy of Sciences, 103, 8577–8582.
   PubMed Web of Science ®Google Scholar
• Newman, M. E., and Girvan, M. (2004), “Finding and Evaluating Community Structure in Networks,” Physical Review E, 69, 026113-1–026113-15.
   Web of Science ®Google Scholar
• Owen, A. B., and Perry, P. O. (2009), “Bi-Cross-Validation of the SVD and the Nonnegative Matrix Factorization,” The Annals of Applied Statistics, 564–594.
   Web of Science ®Google Scholar
• Peixoto, T. P. (2013), “Parsimonious Module Inference in Large Networks,” Physical Review Letters, 110, 148701-1–148701-5.
   Web of Science ®Google Scholar
• Rosvall, M., and Bergstrom, C. T. (2007), “An Information-Theoretic Framework for Resolving Community Structure in Complex Networks,” Proceedings of the National Academy of Sciences, 104, 7327–7331.
   PubMed Web of Science ®Google Scholar
• Saldana, D. F., Yu, Y., and Feng, Y. (2017), “How Many Communities Are There?” Journal of Computational and Graphical Statistics, 26, 171–181.
   Web of Science ®Google Scholar
• Stephens, M. (2000), “Dealing With Label Switching in Mixture Models,” Journal of the Royal Statistical Society, Series B, 62, 795–809.
   Google Scholar
• Sussman, D. L., Tang, M., Fishkind, D. E., and Priebe, C. E. (2012), “A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs,” Journal of the American Statistical Association, 107, 1119–1128.
   Web of Science ®Google Scholar
• Sussman, D. L., Tang, M., and Priebe, C. E. (2013), “Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 36, 48–57.
   Web of Science ®Google Scholar
• Vu, V. (2014), “A Simple SVD Algorithm for Finding Hidden Partitions,” arXiv preprint:1404.3918.
   Google Scholar
• Wang, Y., and Bickel, P. J. (2017), “Likelihood-Based Model Selection for Stochastic Block Models,” The Annals of Statistics, 45, 500–528.
   Web of Science ®Google Scholar
• Yan, X., Shalizi, C., Jensen, J. E., Krzakala, F., Moore, C., Zdeborová, L., Zhang, P., and Zhu, Y. (2014), “Model Selection for Degree-Corrected Block Models,” Journal of Statistical Mechanics: Theory and Experiment, 2014, P05007.
   PubMed Web of Science ®Google Scholar
• Young, S. J., and Scheinerman, E. R. (2007), “Random Dot Product Graph Models for Social Networks,” in Algorithms and Models for the Web-Graph, eds. A. Bonato and F. R. K. Chung, New York: Springer, pp. 138–149.
   Google Scholar
• Zhao, Y., Levina, E., and Zhu, J. (2011), “Community Extraction for Social Networks,” Proceedings of the National Academy of Sciences, 108, 7321–7326.
   PubMed Web of Science ®Google Scholar
• ——— (2012), “Consistency of Community Detection in Networks Under Degree-Corrected Stochastic Block Models,” The Annals of Statistics, 40, 2266–2292.
   Web of Science ®Google Scholar