{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T02:12:56Z","timestamp":1776132776800,"version":"3.50.1"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T00:00:00Z","timestamp":1711756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,9,1]]},"abstract":"<jats:title>Summary<\/jats:title>\n               <jats:p>In many real-world networks, it is often observed that subgraphs or higher-order structures of certain configurations, e.g., triangles and by-fans, are overly abundant compared to standard randomly generated networks (Milo et\u00a0al., 2002). However, statistical models accounting for this phenomenon are limited, especially when community structure is of interest. This limitation is coupled with a lack of community detection methods that leverage subgraphs or higher-order structures. In this paper, we propose a new community detection method that effectively uses higher-order structures in a network. Furthermore, for the community detection accuracy, under an edge-dependent network model that consists of both community and triangle structures, we develop a finite-sample error bound characterized by the expected triangle degree, which leads to the consistency of the proposed method. To the best of our knowledge, this is the first statistical error bound and consistency result for community detection of a single network considering a network model with dependent edges. We also show, in both simulation studies and a real-world data example, that our method unveils network communities that are otherwise invisible to methods that ignore higher-order structures.<\/jats:p>","DOI":"10.1093\/biomet\/asae014","type":"journal-article","created":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T01:01:56Z","timestamp":1711846916000},"page":"903-923","source":"Crossref","is-referenced-by-count":2,"title":["Network community detection using higher-order structures"],"prefix":"10.1093","volume":"111","author":[{"given":"X","family":"Yu","sequence":"first","affiliation":[{"name":"Department of Statistics, University of Michigan , 1085 South University Avenue , Ann Arbor, Michigan 48109, U.S.A"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J","family":"Zhu","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Michigan , 1085 South University Avenue , Ann Arbor, Michigan 48109, U.S.A"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,3,30]]},"reference":[{"key":"2024090418514840400_asae014-B1","first-page":"17","volume-title":"Proc. 23rd Int. Conf. Mach. Learn","author":"Agarwal","year":"2006"},{"key":"2024090418514840400_asae014-B2","first-page":"1981","article-title":"Mixed membership stochastic blockmodels","volume":"9","author":"Airoldi","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"2024090418514840400_asae014-B3","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1038\/nrg2102","article-title":"Network motifs: theory and experimental approaches","volume":"8","author":"Alon","year":"2007","journal-title":"Nature Rev. Genet"},{"key":"2024090418514840400_asae014-B4","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":"2024090418514840400_asae014-B5","doi-asserted-by":"crossref","first-page":"224001","DOI":"10.1088\/1751-8113\/41\/22\/224001","article-title":"Motif-based communities in complex networks","volume":"41","author":"Arenas","year":"2008","journal-title":"J. Phys A"},{"key":"2024090418514840400_asae014-B6","first-page":"19","article-title":"Understanding the wash cycle","volume":"6","author":"Bauer","year":"2001","journal-title":"Econ. Perspect"},{"key":"2024090418514840400_asae014-B7","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1137\/1.9781611974010.14","volume-title":"Proc. 2015 SIAM Int. Conf. Data Mining","author":"Benson","year":"2015"},{"key":"2024090418514840400_asae014-B8","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1126\/science.aad9029","article-title":"Higher-order organization of complex networks","volume":"353","author":"Benson","year":"2016","journal-title":"Science"},{"key":"2024090418514840400_asae014-B9","doi-asserted-by":"crossref","first-page":"21068","DOI":"10.1073\/pnas.0907096106","article-title":"A nonparametric view of network models and Newman\u2013Girvan and other modularities","volume":"106","author":"Bickel","year":"2009","journal-title":"Proc. Nat. Acad. Sci."},{"key":"2024090418514840400_asae014-B10","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1111\/rssb.12289","article-title":"Random-walk models of network formation and sequential Monte Carlo methods for graphs","volume":"80","author":"Bloem-Reddy","year":"2018","journal-title":"J. R. Statist. Soc. B"},{"key":"2024090418514840400_asae014-B11","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1002\/rsa.20322","article-title":"Sparse random graphs with clustering","volume":"38","author":"Bollob\u00e1s","year":"2011","journal-title":"Random Struct. Algor"},{"key":"2024090418514840400_asae014-B12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s00493-004-0002-2","article-title":"The diameter of a scale-free random graph","volume":"24","author":"Bollob\u00e1s","year":"2004","journal-title":"Combinatorica"},{"key":"2024090418514840400_asae014-B13","author":"Chandrasekhar","year":"2023"},{"key":"2024090418514840400_asae014-B14","first-page":"871","volume-title":"Proc. 21st Int. Conf. Artif. Intel. Statist","author":"Chien","year":"2018"},{"key":"2024090418514840400_asae014-B15","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1002\/rsa.20382","article-title":"Upper tails for triangles","volume":"40","author":"Demarco","year":"2012","journal-title":"Random Struct. Algor"},{"key":"2024090418514840400_asae014-B16","article-title":"The geometric block model","author":"Galhotra","year":"2018","journal-title":"In Proc. 32nd AAAI Conf. Artif. Intel., pp. 2215\u201322. Washington, DC: AAAI Press"},{"key":"2024090418514840400_asae014-B17","doi-asserted-by":"crossref","first-page":"2153","DOI":"10.1214\/17-AOS1615","article-title":"Community detection in degree-corrected block models","volume":"46","author":"Gao","year":"2018","journal-title":"Ann. Statist."},{"key":"2024090418514840400_asae014-B18","first-page":"397","volume-title":"Advances in Neural Information Processing Systems","author":"Ghoshdastidar","year":"2014"},{"key":"2024090418514840400_asae014-B19","first-page":"2610","volume-title":"Proc. 29th AAAI Conf. Artif. Intel","author":"Ghoshdastidar","year":"2015"},{"key":"2024090418514840400_asae014-B20","first-page":"400","volume-title":"Proc. 32nd Int. Conf. Mach. Learn","author":"Ghoshdastidar","year":"2015"},{"key":"2024090418514840400_asae014-B21","first-page":"1638","article-title":"Uniform hypergraph partitioning: provable tensor methods and sampling techniques","volume":"18","author":"Ghoshdastidar","year":"2017","journal-title":"J. Mach. Learn. Res"},{"key":"2024090418514840400_asae014-B22","first-page":"2097","volume-title":"2018 IEEE Int. Symp. Info. Theory","author":"Hajek","year":"2018"},{"key":"2024090418514840400_asae014-B23","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":"Social Networks"},{"key":"2024090418514840400_asae014-B24","doi-asserted-by":"crossref","first-page":"9404","DOI":"10.1073\/pnas.0507841103","article-title":"Network motif identification in stochastic networks","volume":"103","author":"Jiang","year":"2006","journal-title":"Proc. Nat. Acad. Sci"},{"key":"2024090418514840400_asae014-B25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1214\/14-AOS1265","article-title":"Fast community detection by SCORE","volume":"43","author":"Jin","year":"2015","journal-title":"Ann. Statist."},{"key":"2024090418514840400_asae014-B26","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":"2024090418514840400_asae014-B27","author":"Ke","year":"2020"},{"key":"2024090418514840400_asae014-B28","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199242726.001.0001","volume-title":"The Collegial Phenomenon: The Social Mechanisms of Cooperation Among Peers in a Corporate Law Partnership","author":"Lazega","year":"2001"},{"key":"2024090418514840400_asae014-B29","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1002\/rsa.20713","article-title":"Concentration and regularization of random graphs","volume":"51","author":"Le","year":"2017","journal-title":"Random Struct. Algor"},{"key":"2024090418514840400_asae014-B30","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. Statist."},{"key":"2024090418514840400_asae014-B31","doi-asserted-by":"crossref","first-page":"11980","DOI":"10.1073\/pnas.2133841100","article-title":"Structure and function of the feed-forward loop network motif","volume":"100","author":"Mangan","year":"2003","journal-title":"Proc. Nat. Acad. Sci"},{"key":"2024090418514840400_asae014-B32","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"2024090418514840400_asae014-B33","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":"2024090418514840400_asae014-B34","author":"Paul","year":"2018"},{"key":"2024090418514840400_asae014-B35","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":"2024090418514840400_asae014-B36","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. Statist."},{"key":"2024090418514840400_asae014-B37","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1111\/rssb.12081","article-title":"Local dependence in random graph models: characterization, properties and statistical inference","volume":"77","author":"Schweinberger","year":"2015","journal-title":"J. R. Statist. Soc. B"},{"key":"2024090418514840400_asae014-B38","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":"2024090418514840400_asae014-B39","first-page":"1451","volume-title":"Proc. 26th Int. Conf. World Wide Web","author":"Tsourakakis","year":"2017"},{"key":"2024090418514840400_asae014-B40","author":"Ugander","year":"2011"},{"key":"2024090418514840400_asae014-B41","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"2024090418514840400_asae014-B42","doi-asserted-by":"crossref","first-page":"4547","DOI":"10.1038\/srep04547","article-title":"Revealing the hidden language of complex networks","volume":"4","author":"Yavero\u011flu","year":"2014","journal-title":"Sci. Rep."},{"key":"2024090418514840400_asae014-B43","doi-asserted-by":"crossref","first-page":"2378","DOI":"10.1214\/20-AOS2042","article-title":"Community detection with dependent connectivity","volume":"49","author":"Yuan","year":"2021","journal-title":"Ann. Statist."},{"key":"2024090418514840400_asae014-B44","first-page":"1601","volume-title":"Advances in Neural Information Processing Systems","author":"Zhou","year":"2006"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asae014\/57322612\/asae014.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/111\/3\/903\/59021257\/asae014.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/111\/3\/903\/59021257\/asae014.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:27:48Z","timestamp":1725535668000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/111\/3\/903\/7638198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,30]]},"references-count":44,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,3,30]]},"published-print":{"date-parts":[[2024,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asae014","relation":{},"ISSN":["0006-3444","1464-3510"],"issn-type":[{"value":"0006-3444","type":"print"},{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,9,1]]},"published":{"date-parts":[[2024,3,30]]}}}