Detecting communities using asymptotical Surprise

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 (14)

• Fast unfolding of communities in large networks
• 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
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Finding statistically significant communities in networks
• Community Structure in Jazz
• 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
• Limited resolution in complex network community detection with Potts model approach
• Surprise maximization reveals the community structure of complex networks

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