{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T15:44:37Z","timestamp":1790696677724,"version":"4.1.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2015,5,21]],"date-time":"2015-05-21T00:00:00Z","timestamp":1432166400000},"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\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1160319"],"award-info":[{"award-number":["DMS-1160319"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,1,1]]},"abstract":"<jats:title>Summary<\/jats:title>\n               <jats:p>Community detection in networks is a key exploratory tool with applications in a diverse set of areas, ranging from finding communities in social and biological networks to identifying link farms in the World Wide Web. The problem of finding communities or clusters in a network has received much attention from statistics, physics and computer science. However, most clustering algorithms assume knowledge of the number of clusters k. We propose to determine k automatically in a graph generated from a stochastic block model by using a hypothesis test of independent interest. Our main contribution is twofold; first, we theoretically establish the limiting distribution of the principal eigenvalue of the suitably centred and scaled adjacency matrix and use that distribution for our test of the hypothesis that a random graph is of Erd\u0151s\u2013R\u00e9nyi (noise) type. Secondly, we use this test to design a recursive bipartitioning algorithm, which naturally uncovers nested community structure. Using simulations and quantifiable classification tasks on real world networks with ground truth, we show that our algorithm outperforms state of the art methods.<\/jats:p>","DOI":"10.1111\/rssb.12117","type":"journal-article","created":{"date-parts":[[2015,5,21]],"date-time":"2015-05-21T17:14:41Z","timestamp":1432228481000},"page":"253-273","source":"Crossref","is-referenced-by-count":124,"title":["Hypothesis Testing for Automated Community Detection in Networks"],"prefix":"10.1093","volume":"78","author":[{"given":"Peter J.","family":"Bickel","sequence":"first","affiliation":[{"name":"University of California at Berkeley , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Purnamrita","family":"Sarkar","sequence":"additional","affiliation":[{"name":"University of Texas at Austin , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2015,5,21]]},"reference":[{"key":"2023021709314864800_rssb12117-cit-0001","volume-title":"Proc. 3rd Int. Wrkshp Link Discovery","author":"Adamic","year":"2005"},{"key":"2023021709314864800_rssb12117-cit-0002","first-page":"1981","article-title":"Mixed membership stochastic blockmodels","volume":"9","author":"Airoldi","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"2023021709314864800_rssb12117-cit-0003","first-page":"692","volume-title":"Advances in Neural Information Processing Systems","author":"Airoldi","year":"2013"},{"key":"2023021709314864800_rssb12117-cit-0004","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. Statist."},{"key":"2023021709314864800_rssb12117-cit-0005","first-page":"268","article-title":"Properties of sufficiency and statistical tests","volume":"160","author":"Bartlett","year":"1937","journal-title":"Proc. R. Soc. Lond."},{"key":"2023021709314864800_rssb12117-cit-0006","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. Natn. Acad. Sci. USA"},{"key":"2023021709314864800_rssb12117-cit-0008","first-page":"1","article-title":"Isotropic local laws for sample covariance and generalized Wigner matrices","volume":"19","author":"Bloemendal","year":"2014","journal-title":"Electron. J. Probab."},{"key":"2023021709314864800_rssb12117-cit-0009","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1214\/14-AOS1272","article-title":"Matrix estimation by universal singular value thresholding","volume":"43","author":"Chatterjee","year":"2015","journal-title":"Ann. Statist."},{"key":"2023021709314864800_rssb12117-cit-0010","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1016\/j.aim.2011.12.010","article-title":"Rigidity of eigenvalues of generalized Wigner matrices","volume":"229","author":"Erd\u0151s","year":"2012","journal-title":"Adv. Math."},{"key":"2023021709314864800_rssb12117-cit-0011","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02579329","article-title":"The eigenvalues of random symmetric matrices","volume":"1","author":"F\u00fcredi","year":"1981","journal-title":"Combinatorica"},{"key":"2023021709314864800_rssb12117-cit-0012","volume-title":"Advances in Neural Information Processing Systems","author":"Hamerly","year":"2003"},{"key":"2023021709314864800_rssb12117-cit-0013","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1111\/j.1467-985X.2007.00471.x","article-title":"Model-based clustering for social networks (with discussion)","volume":"170","author":"Handcock","year":"2007","journal-title":"J. R. Statist. Soc. A"},{"key":"2023021709314864800_rssb12117-cit-0014","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":"Socl Netwrks"},{"key":"2023021709314864800_rssb12117-cit-0015","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":"2023021709314864800_rssb12117-cit-0016","first-page":"16","volume-title":"Proc. 5th Int. Conf. Knowledge Discovery and Data Mining","author":"Larsen","year":"1999"},{"key":"2023021709314864800_rssb12117-cit-0007","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1214\/10-AOAS382","article-title":"Overlapping stochastic block models with application to the French political blogosphere","volume":"5","author":"Latouche","year":"2011","journal-title":"Ann. Appl. Statist"},{"key":"2023021709314864800_rssb12117-cit-0017","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1215\/00127094-2414767","article-title":"A necessary and sufficient condition for edge universality of Wigner matrices","volume":"163","author":"Lee","year":"2014","journal-title":"Duke Math. J."},{"key":"2023021709314864800_rssb12117-cit-0018","volume-title":"A goodness-of-fit test for stochastic block models","author":"Lei","year":"2014"},{"key":"2023021709314864800_rssb12117-cit-0019","first-page":"539","volume-title":"Advances in Neural Information Processing Systems","author":"McAuley","year":"2012"},{"key":"2023021709314864800_rssb12117-cit-0021","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":"2023021709314864800_rssb12117-cit-0022","doi-asserted-by":"crossref","first-page":"14722","DOI":"10.1073\/pnas.1400374111","article-title":"Network histograms and universality of blockmodel approximation","volume":"111","author":"Olhede","year":"2014","journal-title":"Proc. Natn. Acad. Sci. USA"},{"key":"2023021709314864800_rssb12117-cit-0023","volume-title":"Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges","author":"Oliveira","year":"2009"},{"key":"2023021709314864800_rssb12117-cit-0024","doi-asserted-by":"crossref","first-page":"2074","DOI":"10.1371\/journal.pgen.0020190","article-title":"Population structure and eigenanalysis","volume":"2","author":"Patterson","year":"2006","journal-title":"PLOS Genet"},{"key":"2023021709314864800_rssb12117-cit-0025","first-page":"727","volume-title":"Proc. 17th Int. Conf. Machine Learning","author":"Pelleg","year":"2000"},{"key":"2023021709314864800_rssb12117-cit-0026","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1198\/016214502388618906","article-title":"Latent space approaches to social network analysis","volume":"97","author":"Raftery","year":"2002","journal-title":"J. Am. Statist. Ass."},{"key":"2023021709314864800_rssb12117-cit-0020","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1001\/jama.1997.03550100049038","article-title":"Protecting adolescents from harm: findings from the national longitudinal study on adolescent health","volume":"278","author":"Resnick","year":"1997","journal-title":"J. Am. Med. Ass."},{"key":"2023021709314864800_rssb12117-cit-0027","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. Statist."},{"key":"2023021709314864800_rssb12117-cit-0028","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. Classificn"},{"key":"2023021709314864800_rssb12117-cit-0029","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1007\/s002200050743","article-title":"Universality at the edge of the spectrum in Wigner random matrices","volume":"207","author":"Soshnikov","year":"1999","journal-title":"Communs Math. Phys."},{"key":"2023021709314864800_rssb12117-cit-0030","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02100489","article-title":"Level-spacing distributions and the airy kernel","volume":"159","author":"Tracy","year":"1994","journal-title":"Communs Math. Phys."},{"key":"2023021709314864800_rssb12117-cit-0031","doi-asserted-by":"crossref","first-page":"325","DOI":"10.2307\/1970008","article-title":"On the distribution of the roots of certain symmetric matrices","volume":"67","author":"Wigner","year":"1958","journal-title":"Ann. Math."},{"key":"2023021709314864800_rssb12117-cit-0032","first-page":"452","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary","year":"1977","journal-title":"J. Anthr. Res."},{"key":"2023021709314864800_rssb12117-cit-0033","doi-asserted-by":"crossref","first-page":"7321","DOI":"10.1073\/pnas.1006642108","article-title":"Community extraction for social networks","volume":"108","author":"Zhao","year":"2011","journal-title":"Proc. Natn. Acad. Sci. USA"},{"key":"2023021709314864800_rssb12117-cit-0034","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. Statist."}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Frssb.12117","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/78\/1\/253\/49235771\/jrsssb_78_1_253.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/78\/1\/253\/49235771\/jrsssb_78_1_253.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T09:52:07Z","timestamp":1676627527000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/78\/1\/253\/7040688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,21]]},"references-count":34,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2015,5,21]]},"published-print":{"date-parts":[[2016,1,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12117","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2016,1]]},"published":{"date-parts":[[2015,5,21]]}}}