{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:20Z","timestamp":1787337080167,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2023495"],"award-info":[{"award-number":["DMS-2023495"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740850"],"award-info":[{"award-number":["CCF-1740850"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1839317"],"award-info":[{"award-number":["1839317"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1813165"],"award-info":[{"award-number":["1813165"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1908384"],"award-info":[{"award-number":["1908384"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1909790"],"award-info":[{"award-number":["1909790"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF1910294"],"award-info":[{"award-number":["W911NF1910294"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Journal on Mathematics of Data Science"],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A fundamental problem in mathematics and network analysis is to find conditions under which a graph can be partitioned into smaller pieces. A ubiquitous tool for this partitioning is the Fiedler vector or discrete Cheeger inequality. These results relate the graph spectrum (eigenvalues of the normalized adjacency matrix) to the ability to break a graph into two pieces, with few edge deletions. An entire subfield of mathematics, called spectral graph theory, has emerged from these results. Yet these results do not say anything about the rich community structure exhibited by real-world networks, which typically have a significant fraction of edges contained in numerous densely clustered blocks. Inspired by the properties of real-world networks, we discover a new spectral condition that relates eigenvalue powers to a network decomposition into densely clustered blocks. We call this the spectral triadic decomposition. Our relationship exactly predicts the existence of community structure, as commonly seen in real networked data. Our proof provides an efficient algorithm to produce the spectral triadic decomposition. We observe on numerous social, coauthorship, and citation network datasets that these decompositions have significant correlation with semantically meaningful communities.<\/jats:p>","DOI":"10.1137\/23m1586926","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T04:01:56Z","timestamp":1722916916000},"page":"703-730","source":"Crossref","is-referenced-by-count":0,"title":["Spectral Triadic Decompositions of Real-World Networks"],"prefix":"10.1137","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7183-0296","authenticated-orcid":true,"given":"Sabyasachi","family":"Basu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of California, Santa Cruz, CA 95064 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Suman Kalyan","family":"Bera","sequence":"additional","affiliation":[{"name":"Apple Inc., 1 Apple Park Way, Cupertino, CA 95014 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of California, Santa Cruz, CA 95064 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"R. Andersen, F. Chung, and K. Lang, Local graph partitioning using PageRank vectors, in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), IEEE Press, 2006, pp. 475\u2013486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"ref2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1126\/science.aad9029","volume":"353","author":"Benson A.","year":"2016","journal-title":"Science"},{"key":"ref3","doi-asserted-by":"crossref","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"Blondel V. D.","year":"2008","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref4","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1086\/421787","volume":"110","author":"Burt R. S.","year":"2004","journal-title":"Amer. J. Sociol."},{"key":"ref5","unstructured":"C++ Code for Louvain Algorithm, https:\/\/sourceforge.net\/projects\/louvain\/."},{"key":"ref6","doi-asserted-by":"crossref","DOI":"10.1145\/1132952.1132954","volume":"38","author":"Chakrabarti D.","year":"2006","journal-title":"ACM Comput. Surv."},{"key":"ref7","volume-title":"Advances in Neural Information Processing Systems","volume":"25","author":"Chen Y.","year":"2012"},{"key":"ref8","volume-title":"Spectral Graph Theory","author":"Chung F. R. K.","year":"1997"},{"key":"ref9","unstructured":"CDLIB library, https:\/\/pypi.org\/project\/cdlib\/."},{"key":"ref10","first-page":"185","volume":"3","author":"Faust K.","year":"2006","journal-title":"Metodoloski zvezki"},{"key":"ref11","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"Fortunato S.","year":"2010","journal-title":"Phys. Rep."},{"key":"ref12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1073\/pnas.0605965104","volume":"104","author":"Fortunato S.","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref13","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"Girvan M.","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"D. Gleich and C. Seshadhri, Vertex neighborhoods, low conductance cuts, and good seeds for local community methods, in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2012, pp. 597\u2013605.","DOI":"10.1145\/2339530.2339628"},{"key":"ref15","doi-asserted-by":"crossref","first-page":"201","DOI":"10.2307\/202051","volume":"1","author":"Granovetter M.","year":"1983","journal-title":"Sociol. Theor."},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"R. Gupta, T. Roughgarden, and C. Seshadhri, Decompositions of triangle-dense graphs, in Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ACM, 2014, pp. 471\u2013482, https:\/\/doi.org\/10.1145\/2554797.2554840.","DOI":"10.1145\/2554797.2554840"},{"key":"ref17","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1086\/224954","volume":"76","author":"Holland P.","year":"1970","journal-title":"Amer. J. Sociol."},{"key":"ref18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/270703","volume":"7","author":"Holland P. W.","year":"1976","journal-title":"Sociol. Methodol."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"ref20","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1038\/35022643","volume":"406","author":"Kleinberg J.","year":"2000","journal-title":"Nature"},{"key":"ref21","first-page":"557","volume":"309","author":"Lawler G. F.","year":"1988","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2665063","volume":"61","author":"Lee J. R.","year":"2014","journal-title":"J. ACM"},{"key":"ref23","unstructured":"J. Leskovec and A. Krevl, SNAP Datasets: Stanford Large Network Dataset Collection, http:\/\/snap.stanford.edu\/data, June 2014."},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, Statistical properties of community structure in large social and information networks, in Proceedings of the 17th International Conference on World Wide Web (WWW \u201908), ACM, 2008, pp. 695\u2013704.","DOI":"10.1145\/1367497.1367591"},{"key":"ref25","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"Leskovec J.","year":"2009","journal-title":"Internet Math."},{"key":"ref26","first-page":"60","volume":"1","author":"Milgram S.","year":"1967","journal-title":"Psychol. Today"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1073\/pnas.98.2.404","volume":"98","author":"Newman M. E. J.","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref28","doi-asserted-by":"crossref","first-page":"026121","DOI":"10.1103\/PhysRevE.68.026121","volume":"68","author":"Newman M. E. J.","year":"2003","journal-title":"Phys. Rev. E"},{"key":"ref29","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","volume":"103","author":"Newman M. E. J.","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref30","doi-asserted-by":"crossref","first-page":"078301","DOI":"10.1103\/PhysRevLett.117.078301","volume":"117","author":"Newman M. E. J.","year":"2016","journal-title":"Phys. Rev. Lett."},{"key":"ref31","unstructured":"A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic (NIPS\u201901), MIT Press, 2001, pp. 849\u2013856."},{"key":"ref32","first-page":"1423","volume":"40","author":"Peng R.","year":"2015","journal-title":"Proc. Mach. Learn. Res."},{"key":"ref33","unstructured":"PyPI Package: Infomap, https:\/\/pypi.org\/project\/infomap\/."},{"key":"ref34","doi-asserted-by":"crossref","first-page":"2658","DOI":"10.1073\/pnas.0400054101","volume":"101","author":"Radicchi F.","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref35","doi-asserted-by":"crossref","first-page":"036106","DOI":"10.1103\/PhysRevE.76.036106","volume":"76","author":"Raghavan U. N.","year":"2007","journal-title":"Phys. Rev. E"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/080734315"},{"key":"ref37","author":"Rossi R. A.","year":"2015","journal-title":"AAAI"},{"key":"ref38","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1073\/pnas.0706851105","volume":"105","author":"Rosvall M.","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"A. E. Sariyuce, C. Seshadhri, A. Pinar, and U. Catalyurek, Finding the hierarchy of dense subgraphs using nucleus decompositions, in Proceedings of the 24th International Conference on World Wide Web (WWW \u201915), International World Wide Web Conferences Steering Committee, 2015, pp. 927\u2013937, https:\/\/doi.org\/10.1145\/2736277.2741640.","DOI":"10.1145\/2736277.2741640"},{"key":"ref40","doi-asserted-by":"crossref","first-page":"056109","DOI":"10.1103\/PhysRevE.85.056109","volume":"85","author":"Seshadhri C.","year":"2012","journal-title":"Phys. Rev. E"},{"key":"ref41","unstructured":"D. A. Spielman, Spectral and Algebraic Graph Theory, http:\/\/cs-www.cs.yale.edu\/homes\/spielman\/sagt\/."},{"key":"ref42","doi-asserted-by":"crossref","unstructured":"D. A. Spielman, Spectral graph theory and its applications, in IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2007, pp. 29\u201338.","DOI":"10.1109\/FOCS.2007.56"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su, ArnetMiner: Extraction and mining of academic social networks, in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2008, pp. 990\u2013998.","DOI":"10.1145\/1401890.1402008"},{"key":"ref45","doi-asserted-by":"crossref","first-page":"5233","DOI":"10.1038\/s41598-019-41695-z","volume":"9","author":"Traag V.","year":"2019","journal-title":"Sci. Rep."},{"key":"ref46","doi-asserted-by":"crossref","first-page":"4165","DOI":"10.1016\/j.physa.2011.12.021","volume":"391","author":"Traud A. L.","year":"2012","journal-title":"Phys. A"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"C. E. Tsourakakis, The k-clique densest subgraph problem, in Proceedings of the 24th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee, 2015, pp. 1122\u20131132.","DOI":"10.1145\/2736277.2741098"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"C. E. Tsourakakis, J. Pachocki, and M. Mitzenmacher, Scalable motif-aware graph clustering, in Proceedings of the 26th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee, 2017, pp. 1451\u20131460.","DOI":"10.1145\/3038912.3052653"},{"key":"ref49","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences","author":"Wasserman S.","year":"1994"},{"key":"ref50","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"Watts D.","year":"1998","journal-title":"Nature"},{"key":"ref51","doi-asserted-by":"crossref","unstructured":"J. Yang and J. Leskovec, Defining and evaluating network communities based on ground-truth, in Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, ACM, 2012, https:\/\/doi.org\/10.1145\/2350190.2350193.","DOI":"10.1145\/2350190.2350193"}],"container-title":["SIAM Journal on Mathematics of Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1586926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:43:45Z","timestamp":1787334225000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1586926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,6]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1137\/23M1586926"],"URL":"https:\/\/doi.org\/10.1137\/23m1586926","relation":{},"ISSN":["2577-0187"],"issn-type":[{"value":"2577-0187","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,6]]}}}