Well-Connected Community Detection at Extreme Scale: Shared- and Distributed-Memory Parallel Algorithms

Well-Connected Community Detection at Extreme Scale: Shared- and Distributed-Memory Parallel Algorithms | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Well-Connected Community Detection at Extreme Scale: Shared- and Distributed-Memory Parallel Algorithms Mohammed Dindoost, Oliver Alvarado Rodriguez, Asif Uddin, Bartosz Bryg, and 5 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8991284/v1 This work is licensed under a CC BY 4.0 License Status: Under Revision Version 1 posted 7 You are reading this latest preprint version Abstract Community detection algorithms such as Leiden frequently produce clusters thatare internally disconnected or poorly connected, limiting their utility indownstream network analysis. The Well-Connected Clusters (WCC) and ConnectivityModifier (CM) algorithms address this by post-processing any input clusteringto enforce a user-defined edge connectivity criterion through recursive minimumcut bisection. While prior work demonstrated shared-memory parallelimplementations of WCC and CM in Chapel on graphs with up to two billion edges,scalability remains constrained by single-node memory capacity and the cost ofgraph loading and subgraph construction, which together account for over 86%of total runtime on billion-edge inputs.This paper presents distributed-memory parallel implementations of WCC and CMin both C++ with MPI and Chapel with multi-locale execution. The centralcontribution is an architectural redesign that integrates subgraph generationinto the Leiden clustering step, eliminating graph loading and subgraphconstruction from the WCC and CM pipeline entirely. Each compute node receivesonly its assigned subgraph files and executes a fully independent pipelinewithout ever loading the full graph. Connected component computation isparallelized within each node and distributed across nodes via round-robinassignment, and memory-mapped I/O accelerates file loading throughout.Experiments on ten real-world networks spanning up to 2.1 billion edges showthat the C++ distributed implementation achieves up to an order of magnitudespeedup over the original baseline on graphs where both complete successfully.The Chapel distributed implementation is integrated into Arachne, anopen-source graph analytics framework built on the Arkouda platform, availableat https://github.com/Bears-R-Us/arkouda-njit . It successfully processesthe full benchmark suite including graphs on which all other implementationsfail, and delivers consistent 1.2 \((\times)\) --2.1 \((\times)\) speedups over theChapel shared-memory reference. Failures on a subset of large graphs aretraced to a known limitation in the VieCut minimum cut library and are thesubject of ongoing work. Community Detection Complex Networks High-Performance Computing Parallel Algorithms Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Revision Version 1 posted Editorial decision: Revision requested 30 Apr, 2026 Reviews received at journal 16 Mar, 2026 Reviewers agreed at journal 14 Mar, 2026 Reviewers invited by journal 11 Mar, 2026 Editor assigned by journal 03 Mar, 2026 Submission checks completed at journal 01 Mar, 2026 First submitted to journal 27 Feb, 2026 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8991284","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":604482926,"identity":"10a9b66e-4d25-4021-a4ab-0c881755810e","order_by":0,"name":"Mohammed Dindoost","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAsElEQVRIiWNgGAWjYFCC/I8PJCoYmNlAbB7itCQYG1icAWphI0GLmURlG5AmWotue0KCxM15d9j55BsYH7xtI0KL2ZkHBwxnbnsGchiz4VyitNxIbEiW3HYYpIVNmpc4LckMh//OAWth/02kljTGBskGiC3MxGk584aZQeIYSEtis+Scc8RoOZ7D/kOi5nCyfPPhgx/elBGhBQaSGRgYG0hQDwR2pCkfBaNgFIyCEQUAEYQydyKA5QMAAAAASUVORK5CYII=","orcid":"","institution":"New Jersey Institute of Technology","correspondingAuthor":true,"prefix":"","firstName":"Mohammed","middleName":"","lastName":"Dindoost","suffix":""},{"id":604482927,"identity":"ebd233a2-391b-465b-8b50-ad2bc784353a","order_by":1,"name":"Oliver Alvarado Rodriguez","email":"","orcid":"","institution":"New Jersey Institute of Technology","correspondingAuthor":false,"prefix":"","firstName":"Oliver","middleName":"Alvarado","lastName":"Rodriguez","suffix":""},{"id":604482928,"identity":"ad7779b2-93e6-45f1-ba3a-2957cae15337","order_by":2,"name":"Asif Uddin","email":"","orcid":"","institution":"New Jersey Institute of Technology","correspondingAuthor":false,"prefix":"","firstName":"Asif","middleName":"","lastName":"Uddin","suffix":""},{"id":604482929,"identity":"cc8a660c-ff31-4f30-a0e6-d15c50aa3b45","order_by":3,"name":"Bartosz Bryg","email":"","orcid":"","institution":"New Jersey Institute of Technology","correspondingAuthor":false,"prefix":"","firstName":"Bartosz","middleName":"","lastName":"Bryg","suffix":""},{"id":604482930,"identity":"ce32f4d5-7a58-41e4-8411-d073986599a8","order_by":4,"name":"Haotian Yi","email":"","orcid":"","institution":"University of Illinois Urbana-Champaign","correspondingAuthor":false,"prefix":"","firstName":"Haotian","middleName":"","lastName":"Yi","suffix":""},{"id":604482931,"identity":"5367e175-4c77-45e9-90e7-ec0288d060c2","order_by":5,"name":"Minhyuk Park","email":"","orcid":"","institution":"University of Illinois Urbana-Champaign","correspondingAuthor":false,"prefix":"","firstName":"Minhyuk","middleName":"","lastName":"Park","suffix":""},{"id":604482932,"identity":"848ba05b-4939-403a-9ee3-957bb3fd911e","order_by":6,"name":"George Chacko","email":"","orcid":"","institution":"University of Illinois Urbana-Champaign","correspondingAuthor":false,"prefix":"","firstName":"George","middleName":"","lastName":"Chacko","suffix":""},{"id":604482933,"identity":"b71006df-f873-4de4-83c4-462704589ac9","order_by":7,"name":"Tandy Warnow","email":"","orcid":"","institution":"University of Illinois Urbana-Champaign","correspondingAuthor":false,"prefix":"","firstName":"Tandy","middleName":"","lastName":"Warnow","suffix":""},{"id":604482934,"identity":"d8397835-629b-4925-8d92-efb4e5cf475d","order_by":8,"name":"David A. Bader","email":"","orcid":"","institution":"New Jersey Institute of Technology","correspondingAuthor":false,"prefix":"","firstName":"David","middleName":"A.","lastName":"Bader","suffix":""}],"badges":[],"createdAt":"2026-02-27 19:53:19","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8991284/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8991284/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":104781382,"identity":"b1248716-5414-4efa-a99a-4cd7a5946f78","added_by":"auto","created_at":"2026-03-17 07:55:34","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":438052,"visible":true,"origin":"","legend":"","description":"","filename":"WCCandCMPaperJournal.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8991284/v1_covered_f7501090-0e24-4b6b-a86f-7f20ac038d5e.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Well-Connected Community Detection at Extreme Scale: Shared- and Distributed-Memory Parallel Algorithms","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"applied-network-science","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"apns","sideBox":"Learn more about [Applied Network Science](http://appliednetsci.springeropen.com/)","snPcode":"41109","submissionUrl":"https://submission.nature.com/new-submission/41109/3","title":"Applied Network Science","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"Community Detection, Complex Networks, High-Performance Computing, Parallel Algorithms","lastPublishedDoi":"10.21203/rs.3.rs-8991284/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8991284/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eCommunity detection algorithms such as Leiden frequently produce clusters thatare internally disconnected or poorly connected, limiting their utility indownstream network analysis. The Well-Connected Clusters (WCC) and ConnectivityModifier (CM) algorithms address this by post-processing any input clusteringto enforce a user-defined edge connectivity criterion through recursive minimumcut bisection. While prior work demonstrated shared-memory parallelimplementations of WCC and CM in Chapel on graphs with up to two billion edges,scalability remains constrained by single-node memory capacity and the cost ofgraph loading and subgraph construction, which together account for over 86%of total runtime on billion-edge inputs.This paper presents distributed-memory parallel implementations of WCC and CMin both C++ with MPI and Chapel with multi-locale execution. The centralcontribution is an architectural redesign that integrates subgraph generationinto the Leiden clustering step, eliminating graph loading and subgraphconstruction from the WCC and CM pipeline entirely. Each compute node receivesonly its assigned subgraph files and executes a fully independent pipelinewithout ever loading the full graph. Connected component computation isparallelized within each node and distributed across nodes via round-robinassignment, and memory-mapped I/O accelerates file loading throughout.Experiments on ten real-world networks spanning up to 2.1 billion edges showthat the C++ distributed implementation achieves up to an order of magnitudespeedup over the original baseline on graphs where both complete successfully.The Chapel distributed implementation is integrated into Arachne, anopen-source graph analytics framework built on the Arkouda platform, availableat \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://github.com/Bears-R-Us/arkouda-njit\u003c/span\u003e\u003cspan address=\"https://github.com/Bears-R-Us/arkouda-njit\" targettype=\"URL\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e. It successfully processesthe full benchmark suite including graphs on which all other implementationsfail, and delivers consistent 1.2\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\((\\times)\\)\u003c/span\u003e\u003c/span\u003e--2.1\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\((\\times)\\)\u003c/span\u003e\u003c/span\u003e speedups over theChapel shared-memory reference. Failures on a subset of large graphs aretraced to a known limitation in the VieCut minimum cut library and are thesubject of ongoing work.\u003c/p\u003e","manuscriptTitle":"Well-Connected Community Detection at Extreme Scale: Shared- and Distributed-Memory Parallel Algorithms","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-03-13 04:10:12","doi":"10.21203/rs.3.rs-8991284/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2026-04-30T05:56:39+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-03-16T19:28:44+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"168173792210976301291031372927903062657","date":"2026-03-14T10:21:16+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-03-11T11:09:15+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-03-03T10:48:55+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-03-02T04:35:40+00:00","index":"","fulltext":""},{"type":"submitted","content":"Applied Network Science","date":"2026-02-27T19:42:24+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"applied-network-science","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"apns","sideBox":"Learn more about [Applied Network Science](http://appliednetsci.springeropen.com/)","snPcode":"41109","submissionUrl":"https://submission.nature.com/new-submission/41109/3","title":"Applied Network Science","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"ec029735-1565-4972-9efd-aee4411f436d","owner":[],"postedDate":"March 13th, 2026","published":true,"recentEditorialEvents":[{"type":"decision","content":"Revision requested","date":"2026-04-30T05:56:39+00:00","index":"","fulltext":""}],"rejectedJournal":[],"revision":"","amendment":"","status":"in-revision","subjectAreas":[],"tags":[],"updatedAt":"2026-04-30T06:10:10+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-13 04:10:12","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8991284","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8991284","identity":"rs-8991284","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}