Surprise maximization reveals the community structure of complex networks
arXiv:1301.0239 · doi:10.1038/srep01060
Abstract
How to determine the community structure of complex networks is an open question. It is critical to establish the best strategies for community detection in networks of unknown structure. Here, using standard synthetic benchmarks, we show that none of the algorithms hitherto developed for community structure characterization perform optimally. Significantly, evaluating the results according to their modularity, the most popular measure of the quality of a partition, systematically provides mistaken solutions. However, a novel quality function, called Surprise, can be used to elucidate which is the optimal division into communities. Consequently, we show that the best strategy to find the community structure of all the networks examined involves choosing among the solutions provided by multiple algorithms the one with the highest Surprise value. We conclude that Surprise maximization precisely reveals the community structure of complex networks.
8 pages, 6 figures, 2 extra tables. Accepted for publication in Scientific Reports
References in corpus (28)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large 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
- Characterization of complex networks: A survey of measurements
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Community detection in complex networks using Extremal Optimization
- The performance of modularity maximization in practical contexts
- Limits of modularity maximization in community detection
- Detecting Network Communities: a new systematic and efficient algorithm
- Narrow scope for resolution-limit-free community detection
- Multiresolution community detection for megascale networks by information-based replica correlations
- Local resolution-limit-free Potts model for community detection
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Deciphering Network Community Structure by Surprise
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Qualitative Comparison of Community Detection Algorithms
- Hierarchical multiresolution method to overcome the resolution limit in complex networks
- Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering
- Limitation of multi-resolution methods in community detection
- Closed benchmarks for network community structure characterization
Cited by in corpus (23)
- A General Optimization Technique for High Quality Community Detection in Complex Networks
- Significant Scales in Community Structure
- Faster unfolding of communities: speeding up the Louvain algorithm
- Detecting communities using asymptotical Surprise
- Exploring the limits of community detection strategies in complex networks
- Detecting Core-Periphery Structures by Surprise
- On the evaluation potential of quality functions in community detection for different contexts
- Community Detection in Dynamic Networks via Adaptive Label Propagation
- SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
- Identifying multi-scale communities in networks by asymptotic surprise
- Detecting mesoscale structures by surprise
- Multi-resolution community detection in massive networks
- Finding overlapping communities in networks using evolutionary method
- Link community detection through global optimization and the inverse resolution limit of partition density
- Non-overlapping community detection
- Generalized Markov stability of network communities
- Community detection in weighted brain connectivity networks beyond the resolution limit
- An algorithm for network community structure determination by surprise
- Metrics for Community Analysis: A Survey
- Altered Modularity and Disproportional Integration in Functional Networks are Markers of Abnormal Brain Organization in Schizophrenia
- The way to uncover community structure with core and diversity
- The efficiency of community detection by most similar node pairs
- Graph Clustering with Surprise: Complexity and Exact Solutions