# Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection arXiv: https://arxiv.org/abs/2310.10898 ยท HTML: https://mlsanity.com/paper/2310.10898/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Builds on 26 of its 66 references that are in the map. - First posted on arXiv 17 Oct 2023. ## Builds on (most cited first, 26 of 26) - [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) - [Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure](https://mlsanity.com/paper/2002.00843/) (2020) - [Element-centric clustering comparison unifies overlaps and hierarchy](https://mlsanity.com/paper/1706.06136/) (2017) - [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) - [The many facets of community detection in complex networks](https://mlsanity.com/paper/1611.07769/) (2016) - [Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits](https://mlsanity.com/paper/1602.01016/) (2016) - [Normalized mutual information is a biased measure for classification and community detection](https://mlsanity.com/paper/2307.01282/) (2023) - [Detecting communities using asymptotical Surprise](https://mlsanity.com/paper/1503.00445/) (2015) - [Improved mutual information measure for classification and community detection](https://mlsanity.com/paper/1907.12581/) (2019) - [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) - [Consistency of community structure in complex networks](https://mlsanity.com/paper/1908.09867/) (2019) - [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) - [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023) ## Built on by (most cited first, 4 of 4) - [SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion](https://mlsanity.com/paper/2508.14352/) (2025) - [Edge-Wise Graph-Instructed Neural Networks](https://mlsanity.com/paper/2409.08023/) (2024) - [Community detection robustness of graph neural networks](https://mlsanity.com/paper/2509.24662/) (2025) - [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, which involves partitioning nodes within a network, has widespread applications across computational sciences. Modularity-based algorithms identify communities by attempting to maximize the modularity function across network node partitions. Our study assesses the performance of various modularity-based algorithms in obtaining optimal partitions. Our analysis utilizes 104 networks, including both real-world instances from diverse contexts and modular graphs from two families of synthetic benchmarks. We analyze ten inexact modularity-based algorithms against the exact integer programming baseline that globally optimizes modularity. Our comparative analysis includes eight heuristics, two variants of a graph neural network algorithm, and nine variations of the Bayan approximation algorithm. Our findings reveal that the average modularity-based heuristic yields optimal partitions in only 43.9% of the 104 networks analyzed. Graph neural networks and approximate Bayan, on average, achieve optimality on 68.7% and 82.3% of the networks respectively. Additionally, our analysis of three partition similarity metrics exposes substantial dissimilarities between high-modularity sub-optimal partitions and any optimal partition of the networks. We observe that near-optimal partitions are often disproportionately dissimilar to any optimal partition. Taken together, our analysis points to a crucial limitation of the commonly used modularity-based methods: they rarely produce an optimal partition or a partition resembling an optimal partition even on networks with modular structures. If modularity is to be used for detecting communities, we recommend approximate optimization algorithms for a more methodologically sound usage of modularity within its applicability limits.