{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T22:42:30Z","timestamp":1787611350414,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006168","name":"National Nuclear Security Administration","doi-asserted-by":"publisher","award":["DE-NA0003963"],"award-info":[{"award-number":["DE-NA0003963"]}],"id":[{"id":"10.13039\/100006168","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Clustering is a commonplace problem in many areas of data science, with applications in biology and bioinformatics, understanding chemical structure, image segmentation, building recommender systems, and many more fields. While there are many different clustering variants (based on given distance or graph structure, probability distributions, or data density), we consider here the problem of clustering nodes in a graph, motivated by the problem of aggregating discrete degrees of freedom in multigrid and domain decomposition methods for solving sparse linear systems. Specifically, we consider the challenge of forming balanced clusters in the graph of a sparse matrix for use in algebraic multigrid, although the algorithm has general applicability. Based on an extension of the Bellman\u2013Ford algorithm, we generalize Lloyd\u2019s algorithm for partitioning subsets of [Formula: see text] to balance the number of nodes in each cluster; this is accompanied by a rebalancing algorithm that reduces the overall energy in the system. The algorithm provides control over the number of clusters and leads to \u201cwell centered\u201d partitions of the graph. Theoretical results are provided to establish linear complexity and numerical results in the context of algebraic multigrid highlight the benefits of improved clustering.<\/jats:p>\n                  <jats:p>Reproducibility of computational results. This paper has been awarded the \u201cSIAM Reproducibility Badge: Code and data available\u201d as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https:\/\/github.com\/lukeolson\/paper-lloyd-data and in the supplementary materials ( paper-lloyd-data.zip [88.1MB]). [Formula: see text]<\/jats:p>","DOI":"10.1137\/23m1556800","type":"journal-article","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T04:07:21Z","timestamp":1725336441000},"page":"A2819-A2847","source":"Crossref","is-referenced-by-count":3,"title":["Generalizing Lloyd\u2019s Algorithm for Graph Clustering"],"prefix":"10.1137","volume":"46","author":[{"given":"Tareq","family":"Zaman","sequence":"first","affiliation":[{"name":"Interdisciplinary Program in Scientific Computing, Memorial University of Newfoundland, St. John\u2019s, NL A1C 5S7, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Nytko","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Taghibakhshi","sequence":"additional","affiliation":[{"name":"Department of Mechanical Science and Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6364-0684","authenticated-orcid":true,"given":"Scott","family":"MacLachlan","sequence":"additional","affiliation":[{"name":"Interdisciplinary Program in Scientific Computing, Memorial University of Newfoundland, St. John\u2019s, NL A1C 5S7, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5283-6104","authenticated-orcid":true,"given":"Luke","family":"Olson","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew","family":"West","sequence":"additional","affiliation":[{"name":"Department of Mechanical Science and Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,9,3]]},"reference":[{"key":"ref1","unstructured":"D. Arthur and S. Vassilvitskii, K-Means++: The advantages of careful seeding, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, USA, Society for Industrial and Applied Mathematics, 2007, pp. 1027\u20131035."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/110838844"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.21105\/joss.04142"},{"key":"ref4","unstructured":"W. N. Bell, Algebraic Multigrid for Discrete Differential Forms, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2008, http:\/\/hdl.handle.net\/2142\/81820."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_3"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/120876083"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719505"},{"key":"ref8","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2022","edition":"4"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"J. Erickson, Algorithms, 2019, http:\/\/jeffe.cs.illinois.edu\/teaching\/algorithms\/.","DOI":"10.1093\/oxfordhb\/9780190226992.013.32"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2579"},{"key":"ref11","unstructured":"G. Karypis and V. Kumar, METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, 2022, https:\/\/github.com\/KarypisLab\/METIS."},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"B. Kelley and S. Rajamanickam, Parallel, portable algorithms for distance-2 maximal independent set and graph coarsening, in Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE Computer Society, Los Alamitos, CA, 2022, pp. 280\u2013290, https:\/\/doi.org\/10.1109\/IPDPS53621.2022.00035.","DOI":"10.1109\/IPDPS53621.2022.00035"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/040607769"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1930"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082706"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.21136\/AM.1992.104515"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/100818509"},{"key":"ref19","first-page":"123","volume":"37","author":"Notay Y.","year":"2010","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1002\/nla.669"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/2998441"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"ref23","unstructured":"N. Schl\u00f6mer, pygmsh: A Python Frontend for Gmsh, 2022, https:\/\/doi.org\/10.5281\/zenodo.1173105."},{"key":"ref24","first-page":"413","volume-title":"Multigrid","author":"St\u00fcben K.","year":"2001"},{"key":"ref25","volume-title":"Multigrid","author":"Trottenberg U.","year":"2001"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"R. S. Tuminaro and C. Tong, Parallel smoothed aggregation multigrid: Aggregation strategies on massively parallel machines, in SuperComputing 2000 Proceedings, J. Donnelley, ed. 2000, 5.","DOI":"10.1109\/SC.2000.10008"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.21136\/AM.1992.104509"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s211-001-8015-y"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238511"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1556800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:42:45Z","timestamp":1787326965000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1556800"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,3]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1137\/23M1556800"],"URL":"https:\/\/doi.org\/10.1137\/23m1556800","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,3]]}}}