Parallel algorithms push well-connected community detection to billion-edge graphs

Community detection algorithms such as Louvain often return clusters that are internally disconnected or poorly connected, a flaw that limits their usefulness in downstream network analysis. Two post-processing methods, Well-Connected Clusters (WCC) and Connectivity Modifier (CM), address this by taking any input clustering and enforcing a user-defined edge connectivity criterion through recursive minimum cut bisection. A new open-access study in Applied Network Science reports distributed-memory parallel implementations of both algorithms, extending them to graphs far beyond the reach of earlier single-node versions.

Previous work had demonstrated shared-memory parallel implementations of WCC and CM, written in the Chapel language, on graphs with up to two billion edges. But scalability remained constrained in two ways: by the memory capacity of a single node, and by a separate subgraph-construction preprocessing pass in the original pipeline. The new paper tackles both bottlenecks with implementations in C++ with MPI and in Chapel with multi-locale execution.

The central contribution is an architectural redesign that folds subgraph generation directly into the Leiden clustering step, eliminating the separate WCC/CM preprocessing pass entirely. Each compute node receives only its assigned subgraph files and runs a fully independent pipeline, never loading the full graph. Connected component computation is parallelized within each node and distributed across nodes by round-robin assignment, while memory-mapped input and output accelerate file loading throughout.

The performance results come from experiments on ten real-world networks spanning up to 2.1 billion edges. On graphs where both implementations complete successfully, the C++ distributed version achieves speedups of up to 65 times over the original baseline. These are measured comparisons on the tested configurations, not universal guarantees for every graph.

The Chapel distributed implementation is integrated into Arachne, an open-source graph analytics framework built on the Arkouda platform, with code available on GitHub. Notably, it achieves broader graph coverage than the C++ distributed implementations: it successfully processes billion-edge configurations including Open-Alex and Open-Citations, on which all C++ distributed implementations fail. Wikipedia-Links, however, remains unsuccessful for both implementations.

On configurations that complete, the Chapel distributed version delivers speedups of up to 19.7 times at a CPM parameter of 0.001 and up to 55.8 times at CPM 0.01, measured against the Chapel shared-memory reference. The results are not uniformly positive: the authors report one slowdown, on Livejournal WCC at CPM 0.001, an honest caveat in a paper otherwise dominated by large gains.

Failures on a subset of the largest graphs are associated with memory leaks and data races in VieCut, the minimum cut library underlying the connectivity checks. This attribution matters for future work, since it suggests the remaining scaling limits may lie in a dependency rather than in the distributed architecture itself.

The practical significance lies in what well-connected clusters buy for analysts. Because WCC and CM post-process any clustering rather than replacing the detection algorithm, the improvements are portable across pipelines, and the redesign means analysts can run the full workflow on distributed clusters without any single machine holding the entire graph.

The article was published on 28 August 2026 and is open access, with an early-shared version noted as subject to further edits before the final Version of Record. For practitioners working with billion-edge citation networks, web graphs, and social networks, the study offers both working code and a candid account of where extreme-scale community refinement still breaks down.

Subject of Research: Distributed-memory parallel algorithms for well-connected community detection on very large graphs

Article Title: Well-connected community detection at extreme scale: shared- and distributed-memory parallel algorithms

Article References: Dindoost, M., Alvarado Rodriguez, O., Uddin, A., Bryg, B., Yi, H., Park, M., Chacko, G., Warnow, T., & Bader, D. A. (2026). Well-connected community detection at extreme scale: shared- and distributed-memory parallel algorithms. Applied Network Science. https://doi.org/10.1007/s41109-026-00818-y

Image Credits: AI Generated

DOI: 10.1007/s41109-026-00818-y

Keywords: community detection, graph algorithms, distributed memory, MPI, Chapel, parallel computing, edge connectivity, Leiden algorithm, high-performance computing, network analysis, Well-connected, community