Deciphering Network Community Structure by Surprise

Abstract

The analysis of complex networks permeates all sciences, from biology to sociology. A fundamental, unsolved problem is how to characterize the community structure of a network. Here, using both standard and novel benchmarks, we show that maximization of a simple global parameter, which we call Surprise (S), leads to a very efficient characterization of the community structure of complex synthetic networks. Particularly, S qualitatively outperforms the most commonly used criterion to define communities, Newman and Girvan's modularity (Q). Applying S maximization to real networks often provides natural, well-supported partitions, but also sometimes counterintuitive solutions that expose the limitations of our previous knowledge. These results indicate that it is possible to define an effective global criterion for community structure and open new routes for the understanding of complex networks.

7 pages, 5 figures

References in corpus (10)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering

Cited by in corpus (27)

• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Significant Scales in Community Structure
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• Detecting communities using asymptotical Surprise
• Surprise maximization reveals the community structure of complex networks
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• Exploring the limits of community detection strategies in complex networks
• Community structure: A comparative evaluation of community detection methods
• Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Network community detection using modularity density measures
• Extraction of hidden information by efficient community detection in networks
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• Closed benchmarks for network community structure characterization
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Link community detection through global optimization and the inverse resolution limit of partition density
• 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
• Detecting Statistically Significant Communities
• Resolution limit revisited: community detection using generalized modularity density
• Fast community structure local uncovering by independent vertex-centred process
• How Many Political Parties Should Brazil Have? A Data-driven Method to Assess and Reduce Fragmentation in Multi-Party Political Systems
• Metrics for Community Analysis: A Survey
• Graph Clustering with Surprise: Complexity and Exact Solutions
• Approximate Conditional Sampling for Pattern Detection in Weighted Networks