{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:46:59Z","timestamp":1753876019934,"version":"3.41.2"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T00:00:00Z","timestamp":1661212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771241","11931001"],"award-info":[{"award-number":["11771241","11931001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,8,23]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The stochastic block model (SBM) is a popular model for community detecting problems. Many community detecting approaches have been proposed, and most of them assume that the number of communities is given previously. However, in practice, the number of communities is often unknown. Plenty of approaches were proposed to estimate the number of communities, but most of them were computationally intensive. Moreover, when outliers exist, there are no approaches to consistently estimate the number of communities. In this article, we propose a fast method based on the eigenvalues of the regularized and normalized adjacency matrix to estimate the number of communities under the SBM with outliers. We show that our method can consistently estimate the number of communities when outliers exist. Moreover, we extend our method to the degree-corrected SBM. We show that our approach is comparable to the other existing approaches in simulations. We also illustrate our approach on four real-world networks.<\/jats:p>","DOI":"10.1093\/comnet\/cnac042","type":"journal-article","created":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:10:30Z","timestamp":1662768630000},"source":"Crossref","is-referenced-by-count":0,"title":["Estimating the number of communities in the stochastic block model with outliers"],"prefix":"10.1093","volume":"10","author":[{"given":"Jingsong","family":"Xiao","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Tsinghua University , Haidian District, Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5536-7684","authenticated-orcid":false,"given":"Fei","family":"Ye","sequence":"additional","affiliation":[{"name":"School of Statistics, Capital University of Economics and Business , 121 Zhangjialukou, Huaxiang Fengtai District, Beijing 100070, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Ma","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Tsinghua University , Haidian District, Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Tsinghua University , Haidian District, Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,9,9]]},"reference":[{"key":"2022090914281487100_B1","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1109\/43.159993","article-title":"New spectral methods for ratio cut partitioning and clustering","volume":"11","author":"Hagen,","year":"1992","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst."},{"key":"2022090914281487100_B2","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi,","year":"2000","journal-title":"IEEE Trans. Patt. Anal. Mach. Intell."},{"key":"2022090914281487100_B3","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/263867.263872","article-title":"A simple min-cut algorithm","volume":"44","author":"Stoer,","year":"1997","journal-title":"J. ACM"},{"key":"2022090914281487100_B4","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman,","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2022090914281487100_B5","first-page":"026","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman,","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2022090914281487100_B6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato,","year":"2010","journal-title":"Phys. Rep."},{"key":"2022090914281487100_B7","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: first steps","volume":"5","author":"Holland,","year":"1983","journal-title":"Soc. Netw."},{"key":"2022090914281487100_B8","doi-asserted-by":"crossref","first-page":"21068","DOI":"10.1073\/pnas.0907096106","article-title":"A nonparametric view of network models and Newman$-$Girvan and other modularities","volume":"106","author":"Bickel,","year":"2009","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2022090914281487100_B9","doi-asserted-by":"crossref","first-page":"2266","DOI":"10.1214\/12-AOS1036","article-title":"Consistency of community detection in networks under degree-corrected stochastic block models","volume":"40","author":"Zhao,","year":"2012","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B10","doi-asserted-by":"crossref","first-page":"1878","DOI":"10.1214\/11-AOS887","article-title":"Spectral clustering and the high-dimensional stochastic blockmodel","volume":"39","author":"Rohe,","year":"2011","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B11","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1214\/14-AOS1274","article-title":"Consistency of spectral clustering in stochastic block models","volume":"43","author":"Lei,","year":"2015","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B12","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1109\/TIT.2019.2934157","article-title":"Strong consistency of spectral clustering for stochastic block models","volume":"66","author":"Su,","year":"2020","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2022090914281487100_B13","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1214\/16-AOS1447","article-title":"Impact of regularization on spectral clustering","volume":"44","author":"Joseph,","year":"2016","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B14","doi-asserted-by":"crossref","first-page":"962","DOI":"10.1214\/14-AOS1285","article-title":"Role of normalization in spectral clustering for stochastic blockmodels","volume":"43","author":"Sarkar,","year":"2015","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B15","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1080\/01621459.2012.699795","article-title":"A consistent adjacency spectral embedding for stochastic blockmodel graphs","volume":"107","author":"Sussman,","year":"2012","journal-title":"J. Am. Stat. Assoc."},{"key":"2022090914281487100_B16","doi-asserted-by":"crossref","first-page":"2905","DOI":"10.1214\/14-EJS978","article-title":"Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding","volume":"8","author":"Lyzinski,","year":"2014","journal-title":"Electron. J. Stat."},{"key":"2022090914281487100_B17","doi-asserted-by":"crossref","first-page":"2097","DOI":"10.1214\/13-AOS1138","article-title":"Pseudo-likelihood methods for community detection in large sparse networks","volume":"41","author":"Amini,","year":"2013","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B18","first-page":"6446","article-title":"Community detection and stochastic block models: recent developments","volume":"18","author":"Abbe,","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"2022090914281487100_B19","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/s41109-019-0232-2","article-title":"A review of stochastic block models and extensions for graph clustering","volume":"4","author":"Lee,","year":"2019","journal-title":"Appl. Netw. Sci."},{"key":"2022090914281487100_B20","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1214\/14-AOS1290","article-title":"Robust and computationally feasible community detection in the presence of arbitrary outlier nodes","volume":"43","author":"Cai,","year":"2015","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B21","doi-asserted-by":"crossref","first-page":"107308","DOI":"10.1016\/j.csda.2021.107308","article-title":"Outlier detection in networks with missing links","volume":"164","author":"Gaucher,","year":"2021","journal-title":"Comput. Stat. Data Anal."},{"key":"2022090914281487100_B22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s11222-007-9046-7","article-title":"A mixture model for random graphs","volume":"18","author":"Daudin,","year":"2008","journal-title":"Stat. Comput."},{"key":"2022090914281487100_B23","doi-asserted-by":"crossref","first-page":"1771","DOI":"10.1080\/01621459.2019.1637744","article-title":"Corrected Bayesian information criterion for stochastic block models","volume":"115","author":"Hu,","year":"2020","journal-title":"J. Am. Stat. Assoc."},{"key":"2022090914281487100_B24","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1177\/1471082X1001200105","article-title":"Variational Bayesian inference and complexity control for stochastic block models","volume":"12","author":"Latouche,","year":"2012","journal-title":"Stat. Model."},{"key":"2022090914281487100_B25","doi-asserted-by":"crossref","first-page":"148701","DOI":"10.1103\/PhysRevLett.110.148701","article-title":"Parsimonious module inference in large networks","volume":"110","author":"Peixoto,","year":"2013","journal-title":"Phys. Rev. Lett."},{"key":"2022090914281487100_B26","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1080\/10618600.2015.1096790","article-title":"How many communities are there?","volume":"26","author":"Saldaa,","year":"2017","journal-title":"J. Comput. Graph. Stat."},{"key":"2022090914281487100_B27","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1214\/16-AOS1457","article-title":"Likelihood-based model selection for stochastic block models","volume":"45","author":"Wang,","year":"2017","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B28","doi-asserted-by":"crossref","first-page":"1291","DOI":"10.1007\/s11222-020-09946-6","article-title":"Bayesian estimation of the latent dimension and communities in stochastic blockmodels","volume":"30","author":"Passino,","year":"2020","journal-title":"Stat. Comput."},{"key":"2022090914281487100_B29","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/9781119483298.ch11","article-title":"Bayesian stochastic blockmodeling","volume-title":"Advances in Network Clustering and Blockmodeling","author":"Peixoto,","year":"2019","edition":"1st ed"},{"key":"2022090914281487100_B30","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1109\/ASONAM.2016.7752253","article-title":"Bayesian model selection of stochastic block models","volume-title":"2016 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)","author":"Yan,","year":"2016"},{"key":"2022090914281487100_B31","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1080\/01621459.2016.1246365","article-title":"Network cross-validation for determining the number of communities in network data","volume":"113","author":"Chen,","year":"2018","journal-title":"J. Am. Stat. Assoc."},{"author":"Li,","key":"2022090914281487100_B32"},{"key":"2022090914281487100_B33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/01621459.2020.1722676","article-title":"Using maximum entry-wise deviation to test the goodness of fit for stochastic block models","volume":"116","author":"Hu,","year":"2021","journal-title":"J. Am. Stat. Assoc."},{"key":"2022090914281487100_B34","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1214\/15-AOS1370","article-title":"A goodness-of-fit test for stochastic block models","volume":"44","author":"Lei,","year":"2016","journal-title":"Ann. Stat."},{"key":"2022090914281487100_B35","doi-asserted-by":"crossref","first-page":"3315","DOI":"10.1214\/21-EJS1971","article-title":"Estimating the number of communities in networks by spectral methods","volume":"16","author":"Le,","year":"2022","journal-title":"Electron. J. Stat."},{"key":"2022090914281487100_B36","doi-asserted-by":"crossref","first-page":"016107","DOI":"10.1103\/PhysRevE.83.016107","article-title":"Stochastic blockmodels and community structure in networks","volume":"83","author":"Karrer,","year":"2011","journal-title":"Phys. Rev. E"},{"key":"2022090914281487100_B37","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-015-3994-4","volume-title":"Identification of Outliers","author":"Hawkins,","year":"1980"},{"key":"2022090914281487100_B38","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","author":"von Luxburg,","year":"2007","journal-title":"Stat. Comput."},{"key":"2022090914281487100_B39","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1090\/S0002-9939-1955-0067842-9","article-title":"An extremum property of sums of eigenvalues","volume":"6","author":"Wielandt,","year":"1955","journal-title":"Proc. Am. Math. Soc."},{"key":"2022090914281487100_B40","first-page":"3120","article-title":"Regularized spectral clustering under the degree-corrected stochastic blockmodel","volume-title":"Advances in Neural Information Processing Systems","author":"Qin,","year":"2013"},{"key":"2022090914281487100_B41","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s003579900004","article-title":"Estimation and prediction for stochastic blockmodels for graphs with latent block structure","volume":"14","author":"Snijders,","year":"1997","journal-title":"J. Classif."},{"key":"2022090914281487100_B42","doi-asserted-by":"crossref","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","article-title":"Finding community structure in networks using the eigenvectors of matrices","volume":"74","author":"Newman,","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2022090914281487100_B43","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/s00265-003-0651-y","article-title":"The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations","volume":"54","author":"Lusseau,","year":"2003","journal-title":"Behav. Ecol. Sociobiol."},{"key":"2022090914281487100_B44","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary,","year":"1977","journal-title":"J. Anthropol. Res."}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/5\/cnac042\/45758518\/cnac042.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/5\/cnac042\/45758518\/cnac042.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:11:12Z","timestamp":1662768672000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnac042\/6694947"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,23]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,8,23]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnac042","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2022,10,1]]},"published":{"date-parts":[[2022,8,23]]},"article-number":"cnac042"}}