# Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 52 references that are in the map.
- First posted on arXiv 28 Feb 2023.

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

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [A General Optimization Technique for High Quality Community Detection in Complex Networks](https://mlsanity.com/paper/1308.3508/) (2013)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [Hierarchical Graph Clustering using Node Pair Sampling](https://mlsanity.com/paper/1806.01664/) (2018)
- [EdMot: An Edge Enhancement Approach for Motif-aware Community Detection](https://mlsanity.com/paper/1906.04560/) (2019)
- [Community detection in networks: Modularity optimization and maximum likelihood are equivalent](https://mlsanity.com/paper/1606.02319/) (2016)
- [Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits](https://mlsanity.com/paper/1602.01016/) (2016)
- [Detecting communities using asymptotical Surprise](https://mlsanity.com/paper/1503.00445/) (2015)
- [Cover time for random walks on arbitrary complex networks](https://mlsanity.com/paper/1706.02356/) (2017)
- [Community Detection in the Stochastic Block Model by Mixed Integer Programming](https://mlsanity.com/paper/2101.12336/) (2021)
- [Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity](https://mlsanity.com/paper/2209.04562/) (2022)
- [Network community detection using modularity density measures](https://mlsanity.com/paper/1708.06810/) (2017)
- [Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection](https://mlsanity.com/paper/1808.07690/) (2018)
- [Additive Approximation Algorithms for Modularity Maximization](https://mlsanity.com/paper/1601.03316/) (2016)
- [The parameterised complexity of computing the maximum modularity of a graph](https://mlsanity.com/paper/1807.06965/) (2018)

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

- [Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection](https://mlsanity.com/paper/2310.10898/) (2023)
- [Robust Markov stability for community detection at a scale learned based on the structure](https://mlsanity.com/paper/2504.11621/) (2025)

## Abstract (arXiv)

Community detection is a fundamental problem in computational sciences with extensive applications in various fields. The most commonly used methods are the algorithms designed to maximize modularity over different partitions of the network nodes. Using 80 real and random networks from a wide range of contexts, we investigate the extent to which current heuristic modularity maximization algorithms succeed in returning maximum-modularity (optimal) partitions. We evaluate (1) the ratio of the algorithms' output modularity to the maximum modularity for each input graph, and (2) the maximum similarity between their output partition and any optimal partition of that graph. We compare eight existing heuristic algorithms against an exact integer programming method that globally maximizes modularity. The average modularity-based heuristic algorithm returns optimal partitions for only 19.4% of the 80 graphs considered. Additionally, results on adjusted mutual information reveal substantial dissimilarity between the sub-optimal partitions and any optimal partition of the networks in our experiments. More importantly, our results show that near-optimal partitions are often disproportionately dissimilar to any optimal partition. Taken together, our analysis points to a crucial limitation of commonly used modularity-based heuristics for discovering communities: they rarely produce an optimal partition or a partition resembling an optimal partition. If modularity is to be used for detecting communities, exact or approximate optimization algorithms are recommendable for a more methodologically sound usage of modularity within its applicability limits.