Asymptotic resolution bounds of generalized modularity and multi-scale community detection
arXiv:1902.04243 · doi:10.1016/j.ins.2020.03.082
Abstract
The maximization of generalized modularity performs well on networks in which the members of all communities are statistically indistinguishable from each other. However, there is no theory bounding the maximization performance in more realistic networks where edges are heterogeneously distributed within and between communities. Using the random graph properties, we establish asymptotic theoretical bounds on the resolution parameter for which the generalized modularity maximization performs well. From this new perspective on random graph model, we find the resolution limit of modularity maximization can be explained in a surprisingly simple and straightforward way. Given a network produced by the stochastic block models, the communities for which the resolution parameter is larger than their densities are likely to be spread among multiple clusters, while communities for which the resolution parameter is smaller than their background inter-community edge density will be merged into one large component. Therefore, no suitable resolution parameter exits when the intra-community edge density in a subgraph is lower than the inter-community edge density in some other subgraph. For such networks, we propose a progressive agglomerative heuristic algorithm to detect practically significant communities at multiple scales.
References in corpus (24)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Cooperative Game Theory Approaches for Network Partitioning
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Limits of modularity maximization in community detection
- The ground truth about metadata and community detection in networks
- Narrow scope for resolution-limit-free community detection
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Community Detection via Maximization of Modularity and Its Variants
- Evaluating Overfit and Underfit in Models of Network Community Structure
- Significant Scales in Community Structure
- Entropy of stochastic blockmodel ensembles
- Enhancing community detection using a network weighting strategy
- Model Selection for Degree-corrected Block Models
- Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
- Adaptive Modularity Maximization via Edge Weighting Scheme
- A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure