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.
arXiv comment6+6 pages, 5 figures
References in corpus (27)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Resolution limit in community detection
- Community detection algorithms: a comparative analysis
- Stochastic blockmodels and community structure in networks
- The performance of modularity maximization in practical contexts
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral methods for network community detection and graph partitioning
- Phase transition in the detection of modules in sparse networks
- Structure and inference in annotated networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Graph spectra and the detectability of community structure in networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- Estimating the number of communities in a network
- The Nishimori line and Bayesian Statistics
- Detectability of communities in heterogeneous networks
- Spectra of random graphs with community structure and arbitrary degrees
- Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- Algorithmic detectability threshold of the stochastic block model
- Comparative analysis on the selection of number of clusters in community detection
- Global disorder transition in the community structure of large-q Potts systems
- Detectability of the spectral method for sparse graph partitioning
- 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