Identifying multi-scale communities in networks by asymptotic surprise
arXiv:1810.10787 · doi:10.1088/1742-5468/ab00eb
Abstract
Optimizing statistical measures for community structure is one of the most popular strategies for community detection, but many of them lack the flexibility of resolution and thus are incompatible with multi-scale communities of networks. Here, we further studied a statistical measure of interest for community detection, asymptotic surprise, an asymptotic approximation of surprise. We discussed the critical behaviors of asymptotic surprise in phase transition of community partition theoretically. Then, according to the theoretical analysis, a multi-resolution method based on asymptotic surprise was introduced, which provides an alternative approach to study multi-scale networks, and an improved Louvain algorithm was proposed to optimize the asymptotic surprise more effectively. By a series of experimental tests in various networks, we validated the critical behaviors of the asymptotic surprise further and the effectiveness of the improved Louvain algorithm, displayed its ability to solve the first-type resolution limit and stronger tolerance against the second-type resolution limit, and confirmed its effectiveness of revealing multi-scale community structures in multi-scale networks.
arXiv comment18 pages, 7 figures
References in corpus (39)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Statistical Mechanics of Community Detection
- Link communities reveal multiscale complexity in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Community detection in networks: A user guide
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Synchronization reveals topological scales in complex networks
- Consensus clustering in complex networks
- Limits of modularity maximization in community detection
- Analysis of the structure of complex networks at different resolution levels
- Phase transition in the detection of modules in sparse networks
- Detecting network communities by propagating labels under constraints
- Modularity-Maximizing Network Communities via Mathematical Programming
- Graph spectra and the detectability of community structure in networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Multiresolution community detection for megascale networks by information-based replica correlations
- Local resolution-limit-free Potts model for community detection
- Community Structure of the Physical Review Citation Network
- Significant Scales in Community Structure
- Detecting communities using asymptotical Surprise
- Multilayer stochastic block models reveal the multilayer structure of complex networks
- Surprise maximization reveals the community structure of complex networks
- Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
- (Un)detectable cluster structure in sparse networks
- Uncovering the community structure associated with the diffusion dynamics of networks
- Markov random walk under constraint for discovering overlapping communities in complex networks
- Community Detection in Complex Networks Using Density-based Clustering Algorithm
- Limitation of multi-resolution methods in community detection
- Community structure benefits the fixation of cooperation under strong selection
- Multi-resolution community detection based on generalized self-loop rescaling strategy
- Finding network communities using modularity density
- A divisive spectral method for network community detection
- Enhancing community detection by local structural information