# Scalable Community Detection via Parallel Correlation Clustering

arXiv: https://arxiv.org/abs/2108.01731 · HTML: https://mlsanity.com/paper/2108.01731/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 47 references that are in the map.
- First posted on arXiv 27 Jul 2021.

## Builds on (most cited first, 11 of 11)

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks](https://mlsanity.com/paper/1403.3795/) (2014)
- [Faster unfolding of communities: speeding up the Louvain algorithm](https://mlsanity.com/paper/1503.01322/) (2015)
- [Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits](https://mlsanity.com/paper/1602.01016/) (2016)
- [Query-Efficient Correlation Clustering](https://mlsanity.com/paper/2002.11557/) (2020)
- [Parallel Heuristics for Scalable Community Detection](https://mlsanity.com/paper/1410.1237/) (2014)
- [Engineering Parallel Algorithms for Community Detection in Massive Networks](https://mlsanity.com/paper/1304.4453/) (2013)

## Built on by (most cited first, 9 of 9)

- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling](https://mlsanity.com/paper/2306.04884/) (2023)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Constant Approximation for Normalized Modularity and Associations Clustering](https://mlsanity.com/paper/2212.14334/) (2022)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)
- [The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering](https://mlsanity.com/paper/2411.10290/) (2024)
- [Graph Neural Networks with Triangle-Based Messages for the Multicut Problem](https://mlsanity.com/paper/2605.13673/) (2026)

## Abstract (arXiv)

Graph clustering and community detection are central problems in modern data mining. The increasing need for analyzing billion-scale data calls for faster and more scalable algorithms for these problems. There are certain trade-offs between the quality and speed of such clustering algorithms. In this paper, we design scalable algorithms that achieve high quality when evaluated based on ground truth. We develop a generalized sequential and shared-memory parallel framework based on the LambdaCC objective (introduced by Veldt et al.), which encompasses modularity and correlation clustering. Our framework consists of highly-optimized implementations that scale to large data sets of billions of edges and that obtain high-quality clusters compared to ground-truth data, on both unweighted and weighted graphs. Our empirical evaluation shows that this framework improves the state-of-the-art trade-offs between speed and quality of scalable community detection. For example, on a 30-core machine with two-way hyper-threading, our implementations achieve orders of magnitude speedups over other correlation clustering baselines, and up to 28.44x speedups over our own sequential baselines while maintaining or improving quality.