Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
arXiv:2302.14698 · doi:10.1007/978-3-031-36027-5_48
Abstract
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.
arXiv comment15 pages, 3 figures. This is a post-peer-review accepted manuscript from the Proceedings of the 23rd International Conference on Computational Science (ICCS 2023). The publisher authenticated version (version of record) is available on Springer-Nature website https://doi.org/10.1007/978-3-031-36027-5_48
References in corpus (30)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- From Louvain to Leiden: guaranteeing well-connected communities
- Maps of random walks on complex networks reveal community structure
- Resolution limit in community detection
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Community structure in directed networks
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- An information-theoretic framework for resolving community structure in complex networks
- Limits of modularity maximization in community detection
- The ground truth about metadata and community detection in networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Modularity-Maximizing Network Communities via Mathematical Programming
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- A General Optimization Technique for High Quality Community Detection in Complex Networks
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- 20 years of network community detection
- EdMot: An Edge Enhancement Approach for Motif-aware Community Detection
- Deciphering Network Community Structure by Surprise
- Detecting communities using asymptotical Surprise
- Cover time for random walks on arbitrary complex networks
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- Network community detection using modularity density measures
- Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
- Detecting mesoscale structures by surprise
- Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection