On the Optimization of Methods for Establishing Well-Connected Communities
Mohammad Dindoost 1, Oliver Alvarado Rodriguez 1, Bartosz Bryg 1, Minhyuk Park 2, George Chacko 2, Tandy Warnow 2, David A. Bader 1 · 2025
Read On the Optimization of Methods for Establishing Well-Connected Communities by Mohammad Dindoost 1, Oliver Alvarado Rodriguez 1, Bartosz Bryg 1, Minhyuk Park 2, George Chacko 2, Tandy Warnow 2, David A. Bader 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02590.txt.
Introduction
Mohammad Dindoost and six co-authors wrote a 2025 paper on community detection in huge networks. Standard clustering often returns groups that are split or barely linked. Such groups hurt interpretation. Post-processing can fix them, but slowly.
Two repair methods are Well-Connected Clusters and Connectivity Modifier. Both fix weak outputs, yet both crawl on massive graphs. The team rewrote them in Chapel, a parallel language. They also built them into the Arkouda/Arachne analytics framework. The new versions use many cores at once. They handled a network with over two billion edges in minutes on 128 cores. That network is the OpenAlex scholarly graph. The task was out of reach before. The work makes connectivity-preserving clustering practical at web scale.
Catalog record
| CREATOR | Mohammad Dindoost 1, Oliver Alvarado Rodriguez 1, Bartosz Bryg 1, Minhyuk Park 2, George Chacko 2, Tandy Warnow 2, David A. Bader 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-02590
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Optimization of Methods for Establishing Well-Connected Communities Mohammad Dindoost 1, Oliver Alvarado Rodriguez 1, Bartosz Bryg 1, Minhyuk Park 2, George Chacko 2, Tandy Warnow 2, David A. Bader 1 Abstract Community detection plays a central role in uncovering meso scale structures in networks. However, existing methods often suffer from disconnected or weakly connected clusters, undermining interpretability and robustness. Well-Connected Clusters (WCC) and Connectivity Modifier (CM) algorithms are post-processing techniques that improve the accuracy of many clustering methods. However, they are computationally prohibitive on massive graphs. In this work, we present optimized parallel implementations of WCC and CM using the HPE Chapel programming language. First, we design fast and efficient parallel algorithms that leverage Chapel’s parallel constructs to achieve substantial performance improvements and scalability on modern multicore architectures. Second, we integrate this software into Arkouda/Arachne, an open-source, high-performance framework for large-scale graph analytics. Our implementations uniquely enable well-connected community detection on massive graphs with more than 2 billion edges, providing a practical solution for connectivity-preserving clustering at web scale. For example, our implementations of WCC and CM enable community detection of the over 2-billion edge Open-Alex dataset in minutes using 128 cores, a result infeasible to compute previously. † † institute: New Jersey Institute of Technology, Newark, NJ, USA, and University of Illinois Urbana-Champaign Urbana, IL, USA, 1 Introduction Detecting community structure is a foundational problem with broad impact in science and engineering, with applications ranging from cybersecurity akoglu2015graph to biology fortunato2010community and social network analysis newman2004finding . Numerous approaches have been developed to tackle this challenge, including graph partitioning hagen1992new ; karypis1998fast , modularity maximization and its scalable heuristics such as Louvain and Leiden newman2006modularity ; blondel2008fast ; traag2019louvain , probabilistic models such as the stochastic block model (SBM) holland1983stochastic ; abbe2018community ; peixoto2019bayesian , and flow- and motif-based techniques rosvall2008maps ; benson2016higher ; yang2012defining . Although density is often used as the main criterion for communities, ensuring they remain well connected is essential for interpretability and robustness kannan2004clusterings ; traag2019louvain ; park_cm_2024-journal . However, many popular techniques can produce disconnected or weakly linked clusters: modularity-based methods can fragment groups in sparse graphs, and SBM inference may cluster weakly linked vertices together kannan2004clusterings ; fortunato202220 . Such artifacts undermine interpretability and robustness. To address this, methods such as Well-Connected Clusters (WCC) park2024improved-WCC and the Connectivity Modifier (CM) park_cm_2024-journal ; ramavarapu2024cm++ explicitly enforce user-defined intra-community connectivity standards. WCC and CM are post-processing techniques to improve the edge-connectivity of many clustering methods, including SBMs and modularity, and have been shown to produce more accurate community structures compared to traditional approaches park_cm_2024-journal ; park2024improved-WCC . WCC and CM repeatedly refine and split clusters while checking connectivity, leading to significant memory and running-time costs that restrict their use to small- and medium-scale graphs but their use is computationally prohibitive for today’s massive networks with billions of edges. High-performance frameworks such as Arkouda/Arachne rodriguez2022arachne have demonstrated scalable solutions for other graph analytics dindoost2024vf2 ; dindoost2025hipermotif , but connectivity-preserving clustering has not yet been incorporated. We address this scalability gap by developing optimized parallel implementations of WCC and CM in the Chapel programming language chamberlain2007parallel , integrated into the open-source Arkouda/Arachne graph analytics framework rodriguez2022arachne . Our contributions are twofold: 1. Novel Parallel Algorithms: Chapel-based WCC and CM redesigns that reduce redundant work, increase concurrency, and achieve substantial performance improvements. 2. Integration into Arachne: Arachne now supports community detection with well-connectedness guarantees for practical large-scale use. By combining rigorous enforcement of well-connectedness with high-performance computing (HPC)-level scalability, our approach makes well-connected community detection feasible for networks at previously unattainable scale. Our parallel implementations of WCC and CM are freely-available as open source from GitHub: at https://github.com/Bears-R-Us/arkouda-njit . 2 Methods for Establishing Well-Connected Communities In this section, we introduce highly-scalable parallel algorithms and their implementations of the WCC and CM methods. The initial WCC algorithm, implemented in C++ with OpenMP parallelism, employs a shared work-queue model: the initial clusters populate a common queue accessible to all OpenMP threads, with each worker pulling the next cluster to process and pushing any new clusters generated back into the queue. For the CM algorithm, first implemented in Python and parallelized using the multiprocessing module, the initial set of clusters is evenly divided among worker processes, each handling its assigned clusters. Our new approach in this paper extends the original methods by incorporating scalable parallel computing strategies while preserving the guarantees of WCC and CM that all returned clusters are well-connected. Whereas the initial implementations relied on queue-based task management, our Chapel implementations generalize this to a recursive framework that operates over a large collection of initial clusters, treating them as independent subgraphs, and thereby enabling more flexible and scalable processing. WCC and CM share a common structure: both begin with a phase – connected component refinement ( CCR ) – that ensures that all input clusters are internally connected, and both apply recursive refinement to evaluate and partition clusters based on global minimum cut criteria. In both algorithms, subgraphs that satisfy a user-defined metric, typically based on cut size relative to graph size, are accepted and stored, while those that fail are recursively subdivided. The key difference lies in how they handle subgraphs that do not meet the well-connectedness criterion. WCC always bisects such subgraphs using their minimum cut, applying further recursion to the resulting parts. In contrast, CM employs another approach by incorporating a user-selected community detection algorithm (referred to as CDA henceforth, where CDA can be Leiden or any other community detection method) as a refinement step. Following the established methodology, when a subgraph fails the well-connectedness criterion, after removing the min-cut to partition the cluster into two parts, CM applies the chosen community detection method to each resulting part to identify community structure. If multiple communities are found within a part, CM recurses on each community separately; otherwise, it processes the entire part as a single unit. This approach allows CM to identify semantically meaningful substructures by first removing weak connections and then leveraging the user’s preferred community detection method to find cohesive groups within the resulting components. As mentioned previously, both WCC and CM rely on a user-defined criterion function to determine whether a given subgraph is sufficiently well-connected. This function typically takes the form f(n) , where n is the number of vertices in the subgraph under consideration. Common choices for f include logarithmic and sublinear functions such as \log_{10}(n) , \log_{2}(n) , \sqrt{n} , as well as linear functions such as kn , where k is a user-specified constant. The flexibility of this criterion allows users to tailor the sensitivity of the connectivity check to the size and structure of their input graphs. 2.1 Optimized Parallel Implementations Our parallel implementations achieve performance improvements through several key optimizations tailored for large-scale graph processing in the Chapel programming language chamberlain2007parallel . Chapel’s high-level parallel constructs, including forall loops for parallel iteration, built-in parallel reductions, and domain-based parallelism, provide natural optimization opportunities for graph algorithms. The language’s ability to handle large-scale data structures and its built-in support for parallel collections with thread-safe operations eliminate many low-level synchronization concerns while maintaining high performance. Inside the open-source Arkouda/Arachne framework graphs are stored in double-index (DI) format