# Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2016.

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

- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity](https://mlsanity.com/paper/2209.04562/) (2022)
- [Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection](https://mlsanity.com/paper/2310.10898/) (2023)
- [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023)
- [Constant Approximation for Normalized Modularity and Associations Clustering](https://mlsanity.com/paper/2212.14334/) (2022)
- [Unsupervised Optimisation of GNNs for Node Clustering](https://mlsanity.com/paper/2402.07845/) (2024)
- [Robust Markov stability for community detection at a scale learned based on the structure](https://mlsanity.com/paper/2504.11621/) (2025)

## Abstract (arXiv)

Many social networks and complex systems are found to be naturally divided into clusters of densely connected nodes, known as community structure (CS). Finding CS is one of fundamental yet challenging topics in network science. One of the most popular classes of methods for this problem is to maximize Newman's modularity. However, there is a little understood on how well we can approximate the maximum modularity as well as the implications of finding community structure with provable guarantees. In this paper, we settle definitely the approximability of modularity clustering, proving that approximating the problem within any (multiplicative) positive factor is intractable, unless P = NP. Yet we propose the first additive approximation algorithm for modularity clustering with a constant factor. Moreover, we provide a rigorous proof that a CS with modularity arbitrary close to maximum modularity QOPT might bear no similarity to the optimal CS of maximum modularity. Thus even when CS with near-optimal modularity are found, other verification methods are needed to confirm the significance of the structure.