Detecting communities using asymptotical Surprise
arXiv:1503.00445 · doi:10.1103/PhysRevE.92.022816
Abstract
Nodes in real-world networks are repeatedly observed to form dense clusters, often referred to as communities. Methods to detect these groups of nodes usually maximize an objective function, which implicitly contains the definition of a community. We here analyze a recently proposed measure called surprise, which assesses the quality of the partition of a network into communities. In its current form, the formulation of surprise is rather difficult to analyze. We here therefore develop an accurate asymptotic approximation. This allows for the development of an efficient algorithm for optimizing surprise. Incidentally, this leads to a straightforward extension of surprise to weighted graphs. Additionally, the approximation makes it possible to analyze surprise more closely and compare it to other methods, especially modularity. We show that surprise is (nearly) unaffected by the well known resolution limit, a particular problem for modularity. However, surprise may tend to overestimate the number of communities, whereas they may be underestimated by modularity. In short, surprise works well in the limit of many small communities, whereas modularity works better in the limit of few large communities. In this sense, surprise is more discriminative than modularity, and may find communities where modularity fails to discern any structure.
References in corpus (33)
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- Statistical mechanics of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Finding statistically significant communities in networks
- Community Structure in Jazz
- The performance of modularity maximization in practical contexts
- Limits of modularity maximization in community detection
- Phase transition in the detection of modules in sparse networks
- Narrow scope for resolution-limit-free community detection
- Graph spectra and the detectability of community structure in networks
- Local resolution-limit-free Potts model for community detection
- Limited resolution in complex network community detection with Potts model approach
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- Significant Scales in Community Structure
- Deciphering Network Community Structure by Surprise
- Surprise maximization reveals the community structure of complex networks
- Exploring the limits of community detection strategies in complex networks
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Detectability of communities in heterogeneous networks
- Limitation of multi-resolution methods in community detection
- A paradox in community detection
- SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
Cited by in corpus (20)
- Faster unfolding of communities: speeding up the Louvain algorithm
- Community structure: A comparative evaluation of community detection methods
- Link-Prediction Enhanced Consensus Clustering for Complex Networks
- Detecting Core-Periphery Structures by Surprise
- On the evaluation potential of quality functions in community detection for different contexts
- Community structure in the World Trade Network based on communicability distances
- Identifying multi-scale communities in networks by asymptotic surprise
- Identifying Crisis Response Communities in Online Social Networks for Compound Disasters: The Case of Hurricane Laura and Covid-19
- Detecting mesoscale structures by surprise
- Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
- Statistical test for detecting community structure in real-valued edge-weighted graphs
- Link community detection through global optimization and the inverse resolution limit of partition density
- Generalized Markov stability of network communities
- Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- Community detection in weighted brain connectivity networks beyond the resolution limit
- Metrics for Community Analysis: A Survey
- Altered Modularity and Disproportional Integration in Functional Networks are Markers of Abnormal Brain Organization in Schizophrenia
- Thermodynamics of the Minimum Description Length on Community Detection
- Learning dynamic representations of the functional connectome in neurobiological networks
- Binomial Tails for Community Analysis