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.
36 pages, 11 figures
References in corpus (21)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- 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
- An information-theoretic framework for resolving community structure in complex networks
- Narrow scope for resolution-limit-free community detection
- Modularity-Maximizing Network Communities via Mathematical Programming
- Size reduction of complex networks preserving modularity
- Community detection in networks: Structural communities versus ground truth
- 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
- A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
- PyGenStability: Multiscale community detection with generalized Markov Stability