{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:50:38Z","timestamp":1767340238303,"version":"3.41.2"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2020,12,1]],"date-time":"2020-12-01T00:00:00Z","timestamp":1606780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,3,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Many clustering algorithms for complex networks depend on the choice for the number of clusters and it is often unclear how to make this choice. The number of eigenvalues located outside a circle in the spectrum of the non-backtracking matrix was conjectured to be an estimator of the number of clusters in a graph. We compare the estimate of the number of clusters obtained from the spectrum of the non-backtracking matrix with three estimators based on the concept of modularity and evaluate the methods on several benchmark graphs. We find that the non-backtracking method detects the number of clusters better than the modularity-based methods for the graphs in our simulation study, especially when the clusters have slightly different sizes. The estimates of the non-backtracking method are narrowly distributed around the true number of clusters for all benchmark graphs considered. Additionally, for graphs without a clustering structure, the non-backtracking method detects exactly one cluster, which is a convenient property of an estimator of the number of clusters. However, the lack of a well-defined concept of a cluster prevents sharp conclusions.<\/jats:p>","DOI":"10.1093\/comnet\/cnaa047","type":"journal-article","created":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T12:37:42Z","timestamp":1606999062000},"source":"Crossref","is-referenced-by-count":5,"title":["Detecting the number of clusters in a network"],"prefix":"10.1093","volume":"8","author":[{"given":"Gabriel","family":"Budel","sequence":"first","affiliation":[{"name":"Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands"}]},{"given":"Piet","family":"Van Mieghem","sequence":"additional","affiliation":[{"name":"Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands"}]}],"member":"286","published-online":{"date-parts":[[2021,3,7]]},"reference":[{"key":"2021031111200422700_B1","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":"2021031111200422700_B2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s41109-017-0023-6","article-title":"The many facets of community detection in complex networks","volume":"2","author":"Schaub,","year":"2017","journal-title":"Appl. Netw. Sci."},{"key":"2021031111200422700_B3","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":"2021031111200422700_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":"2021031111200422700_B5","doi-asserted-by":"crossref","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman,","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2021031111200422700_B6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921681","author":"Van Mieghem,","year":"2010","journal-title":"Graph Spectra for Complex Networks"},{"key":"2021031111200422700_B7","doi-asserted-by":"crossref","first-page":"20935","DOI":"10.1073\/pnas.1312486110","article-title":"Spectral redemption in clustering sparse networks","volume":"110","author":"Krzakala,","year":"2013","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2021031111200422700_B8","doi-asserted-by":"crossref","first-page":"056113","DOI":"10.1103\/PhysRevE.82.056113","article-title":"Spectral graph analysis of modularity and assortativity","volume":"82","author":"Van Mieghem,","year":"2010","journal-title":"Phys. Rev. E"},{"key":"2021031111200422700_B9","doi-asserted-by":"crossref","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","article-title":"Fast unfolding of communities in large networks","volume":"2008","author":"Blondel,","year":"2008","journal-title":"J. Stat. Mech."},{"key":"2021031111200422700_B10","doi-asserted-by":"crossref","first-page":"056114","DOI":"10.1103\/PhysRevE.80.056114","article-title":"Spectral properties of networks with community structure","volume":"80","author":"Chauhan,","year":"2009","journal-title":"Phys. Rev. E"},{"key":"2021031111200422700_B11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s000260300002","article-title":"Eigenvalues of random power law graphs","volume":"7","author":"Chung,","year":"2003","journal-title":"Ann. Combin."},{"key":"2021031111200422700_B12","article-title":"Line orthogonality in adjacency eigenspace with application to community partition","author":"Wu,","year":"2011","journal-title":"Twenty-Second International Joint Conference on Artificial Intelligence"},{"journal-title":"The Algebraic Eigenvalue Problem","year":"1965","author":"Wilkinson,","key":"2021031111200422700_B13"},{"journal-title":"Matrix Perturbation Theory","year":"1990","author":"Stewart,","key":"2021031111200422700_B14"},{"key":"2021031111200422700_B15","doi-asserted-by":"crossref","first-page":"065701","DOI":"10.1103\/PhysRevLett.107.065701","article-title":"Inference and phase transitions in the detection of modules in sparse networks","volume":"107","author":"Decelle,","year":"2011","journal-title":"Phys. Rev. Lett."},{"key":"2021031111200422700_B16","doi-asserted-by":"crossref","first-page":"078301","DOI":"10.1103\/PhysRevLett.117.078301","article-title":"Estimating the number of communities in a network","volume":"117","author":"Newman,","year":"2016","journal-title":"Phys. Rev. Lett."},{"key":"2021031111200422700_B17","doi-asserted-by":"crossref","first-page":"P10020","DOI":"10.1088\/1742-5468\/2010\/10\/P10020","article-title":"Spectral methods for the detection of network community structure: a comparative analysis","volume":"2010","author":"Shen,","year":"2010","journal-title":"J. Stat. Mech."},{"key":"2021031111200422700_B18","doi-asserted-by":"crossref","first-page":"046110","DOI":"10.1103\/PhysRevE.78.046110","article-title":"Benchmark graphs for testing community detection algorithms","volume":"78","author":"Lancichinetti,","year":"2008","journal-title":"Physical Review E"},{"key":"2021031111200422700_B19","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1109\/MILCOM.2013.32","article-title":"Automatic selection of number of clusters in networks using relative eigenvalue quality","author":"Shea,","year":"2013","journal-title":"MILCOM 2013-2013 IEEE Military Communications Conference"},{"key":"2021031111200422700_B20","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."},{"key":"2021031111200422700_B21","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1177\/1471082X15577017","article-title":"Model selection and clustering in stochastic block models based on the exact integrated complete data likelihood","volume":"15","author":"C\u00f4me,","year":"2015","journal-title":"Stat. Model."},{"key":"2021031111200422700_B22","doi-asserted-by":"crossref","first-page":"032310","DOI":"10.1103\/PhysRevE.96.032310","article-title":"Efficient method for estimating the number of communities in a network","volume":"96","author":"Riolo,","year":"2017","journal-title":"Phys. Rev. E"},{"key":"2021031111200422700_B23","doi-asserted-by":"crossref","first-page":"012317","DOI":"10.1103\/PhysRevE.95.012317","article-title":"Nonparametric Bayesian inference of the microcanonical stochastic block model","volume":"95","author":"Peixoto,","year":"2017","journal-title":"Phys. Rev. E"},{"key":"2021031111200422700_B24","first-page":"211","article-title":"Zeta functions of finite graphs and representations of p-adic groups","author":"Hashimoto,","year":"1989","journal-title":"Automorphic forms and geometry of arithmetic varieties"},{"key":"2021031111200422700_B25","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1073\/pnas.0605965104","article-title":"Resolution limit in community detection","volume":"104","author":"Fortunato,","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2021031111200422700_B26","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."},{"key":"2021031111200422700_B27","first-page":"539","article-title":"Learning to discover social circles in ego networks","volume":"25","author":"Leskovec,","year":"2012","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"2021031111200422700_B28","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":"2021031111200422700_B29","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: densification and shrinking diameters","volume":"1","author":"Leskovec,","year":"2007","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"2021031111200422700_B30","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1109\/FOCS.2015.86","article-title":"Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs","author":"Bordenave,","year":"2015","journal-title":"2015 IEEE 56th Annual Symposium on Foundations of Computer Science"},{"key":"2021031111200422700_B31","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1006\/aima.1996.0050","article-title":"Zeta functions of finite graphs and coverings","volume":"121","author":"Stark,","year":"1996","journal-title":"Adv. Math."},{"key":"2021031111200422700_B32","doi-asserted-by":"crossref","first-page":"4287","DOI":"10.1090\/S0002-9947-2014-06255-7","article-title":"The non-backtracking spectrum of the universal cover of a graph","volume":"367","author":"Angel,","year":"2015","journal-title":"Trans. Am. Math. Soc."},{"journal-title":"Matrix Computations.","year":"1996","author":"Golub,","key":"2021031111200422700_B33"},{"key":"2021031111200422700_B34","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719628","author":"Lehoucq,","year":"1998","journal-title":"ARPACK User\u2019s Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods"},{"journal-title":"MATLAB version 9.5.0.944444 (R2018b)","year":"2017","key":"2021031111200422700_B35"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/6\/cnaa047\/36510011\/cnaa047.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/6\/cnaa047\/36510011\/cnaa047.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T12:08:32Z","timestamp":1615464512000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnaa047\/6161499"}},"subtitle":[],"editor":[{"given":"Ernesto","family":"Estrada","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,12,1]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,3,7]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnaa047","relation":{},"ISSN":["2051-1310","2051-1329"],"issn-type":[{"type":"print","value":"2051-1310"},{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2020,12,1]]},"published":{"date-parts":[[2020,12,1]]},"article-number":"cnaa047"}}