Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.02590 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918134479323136 |
|---|---|
| author | Dindoost, Mohammad Rodriguez, Oliver Alvarado Bryg, Bartosz Park, Minhyuk Chacko, George Warnow, Tandy Bader, David A. |
| author_facet | Dindoost, Mohammad Rodriguez, Oliver Alvarado Bryg, Bartosz Park, Minhyuk Chacko, George Warnow, Tandy Bader, David A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02590 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Optimization of Methods for Establishing Well-Connected Communities Dindoost, Mohammad Rodriguez, Oliver Alvarado Bryg, Bartosz Park, Minhyuk Chacko, George Warnow, Tandy Bader, David A. Social and Information Networks Distributed, Parallel, and Cluster Computing 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. |
| title | On the Optimization of Methods for Establishing Well-Connected Communities |
| topic | Social and Information Networks Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2509.02590 |