Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
arXiv:1808.07690 · doi:10.1103/PhysRevE.99.010301
Abstract
Modularity maximization using greedy algorithms continues to be a popular approach toward community detection in graphs, even after various better forming algorithms have been proposed. Apart from its clear mechanism and ease of implementation, this approach is persistently popular because, presumably, its risk of algorithmic failure is not well understood. This Rapid Communication provides insight into this issue by estimating the algorithmic performance limit of modularity maximization. This is achieved by counting the number of metastable states under a local update rule. Our results offer a quantitative insight into the level of sparsity at which a greedy algorithm typically fails.
6+6 pages, 5 figures
References in corpus (11)
- Fast unfolding of communities in large networks
- Resolution limit in community detection
- Stochastic blockmodels and community structure in networks
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- Algorithmic detectability threshold of the stochastic block model
- Global disorder transition in the community structure of large-q Potts systems
- Community Detection and Stochastic Block Models
- Algorithmic infeasibility of community detection in higher-order networks
Cited by in corpus (5)
- Community Detection in Bipartite Networks with Stochastic Blockmodels
- Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
- Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- Single-trajectory map equation
- Statistical mechanics of the minimum vertex cover problem in stochastic block models