Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
arXiv:2209.04562 · doi:10.1103/PhysRevE.110.044315
Abstract
Community detection is a classic network problem with extensive applications in various fields. Its most common method is using modularity maximization heuristics which rarely return an optimal partition or anything similar. Partitions with globally optimal modularity are difficult to compute, and therefore have been underexplored. Using structurally diverse networks, we compare 30 community detection methods including our proposed algorithm that offers optimality and approximation guarantees: the Bayan algorithm. Unlike existing methods, Bayan globally maximizes modularity or approximates it within a factor. Our results show the distinctive accuracy and stability of maximum-modularity partitions in retrieving planted partitions at rates higher than most alternatives for a wide range of parameter settings in two standard benchmarks. Compared to the partitions from 29 other algorithms, maximum-modularity partitions have the best medians for description length, coverage, performance, average conductance, and well clusteredness. These advantages come at the cost of additional computations which Bayan makes possible for small networks (networks that have up to 3000 edges in their largest connected component). Bayan is several times faster than using open-source and commercial solvers for modularity maximization, making it capable of finding optimal partitions for instances that cannot be optimized by any other existing method. Our results point to a few well performing algorithms, among which Bayan stands out as the most reliable method for small networks. A Python implementation of the Bayan algorithm (bayanpy) is publicly available through the package installer for Python.
arXiv comment36 pages, 11 figures
References in corpus (43)
- Fast unfolding of communities in large networks
- Community structure in social and biological 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
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Statistical Mechanics of 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
- 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
- Structure and inference in annotated networks
- Narrow scope for resolution-limit-free community detection
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Modularity-Maximizing Network Communities via Mathematical Programming
- Size reduction of complex networks preserving modularity
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Community detection in networks: Structural communities versus ground truth
- 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
- The many facets of community detection in complex networks
- Significant Scales in Community Structure
- Element-centric clustering comparison unifies overlaps and hierarchy
- Detecting communities using asymptotical Surprise
- Statistical inference of assortative community structures
- Improved mutual information measure for classification and community detection
- Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure
- Identifying hidden coalitions in the US House of Representatives by optimally partitioning signed networks based on generalized balance
- Detecting mesoscale structures by surprise
- Comparative analysis on the selection of number of clusters in community detection
- A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
- Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
- PyGenStability: Multiscale community detection with generalized Markov Stability
- Subnetwork Constraints for Tighter Upper Bounds and Exact Solution of the Clique Partitioning Problem