Deciphering Network Community Structure by Surprise

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.

• Publication year

  2011

• Venue

  PLoS ONE

• Publication date

  2011-05-12

• Fields of study

  Biology, Medicine, Physics, Computer Science, Sociology

• Identifiers
  DOI 10.1371/journal.pone.0024195arXiv 1105.2459PMID 21909420PMCID 3164713
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• The BioGRID interaction database: 2013 update

  2012cited by this paper
• Mitochondrial dysfunction - the beginning of the end in Alzheimer's disease? Separate and synergistic modes of tau and amyloid-β toxicity

  2011cited by this paper
• Journal of Statistical Mechanics: Theory and Experiment

  2011cited by this paper
• Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering

  2010cited by this paper
• Electron – molecule collision calculations using the R-matrix method

  2010cited by this paper
• Networks: An Introduction

  2010cited by this paper
• Community detection algorithms: a comparative analysis: invited presentation, extended abstract

  2009influential reference
• Community detection in graphs

  2009cited by this paper
• The rank of the covariance matrix of an evanescent field

  2008cited by this paper
• Up-to-date catalogues of yeast protein complexes

  2008influential reference
• Multiresolution community detection for megascale networks by information-based replica correlations.

  2008cited by this paper
• Benchmark graphs for testing community detection algorithms.

  2008influential reference
• Fast unfolding of communities in large networks

  2008cited by this paper
• The BioGRID Interaction Database: 2008 update

  2007cited by this paper
• Comparing clusterings---an information based distance

  2007cited by this paper
• Maps of random walks on complex networks reveal community structure

  2007cited by this paper
• Resolution limit in community detection

  2006influential reference
• Comparative genomics and protein domain graph analyses link ubiquitination and RNA metabolism.

  2006cited by this paper
• Modularity and community structure in networks.

  2006cited by this paper
• Characterization of complex networks: A survey of measurements

  2005cited by this paper
• Comparing community structure identification

  2005cited by this paper
• Iterative Cluster Analysis of Protein Interaction Data

  2005cited by this paper
• Community detection in complex networks using extremal optimization.

  2005cited by this paper
• Network biology: understanding the cell's functional organization

  2004cited by this paper
• Finding and evaluating community structure in networks.

  2003cited by this paper
• Exploring complex networks

  2001cited by this paper
• Small Worlds: The Dynamics of Networks between Order and Randomness

  2001cited by this paper
• Community structure in social and biological networks

  2001influential reference
• Small Worlds: The Dynamics of Networks between Order and Randomness

  1999cited by this paper
• Social Network Analysis: Methods and Applications

  1994cited by this paper
• Finding groups with a simple genetic algorithm

  1993cited by this paper
• Proceedings of the National Academy of Sciences of the United States of America. Annual subject and author indexes.

  1990cited by this paper
• An Information Flow Model for Conflict and Fission in Small Groups

  1977cited by this paper
• The measurement of diversity in different types of biological collections

  1966influential reference
• Journal of Molecular Biology

  1959cited by this paper
• ON THE RELATIVE ABUNDANCE OF BIRD SPECIES.

  1957cited by this paper
• Proceedings of the National Academy of Sciences

  1914cited by this paper
• PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES.

  year unknowncited by this paper
• BMC Systems Biology

  year unknowncited by this paper
• PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES.

  year unknowncited by this paper

• Unveiling emerging communities: a network approach on transport decarbonisation technology

  2026cites this paper
• Impacts of mobility and social networks on social activity-travel participation using location-based social network data

  2026cites this paper
• Null-adjusted persistence function for high-resolution community detection

  2025cites this paper
• Complex networks applied to political analysis: Group voting behavior in the Brazilian congress

  2025cites this paper
• Boosting Task Scheduling Data Locality with Low-latency, HW-accelerated Label Propagation

  2025cites this paper
• An Optimal Transport approach to model the community structure of the International Trade Network

  2025cites this paper
• Strategies for improving the quality of community detection based on modularity optimization

  2024cites this paper
• CSIM: A Fast Community Detection Algorithm Based on Structure Information Maximization

  2024cites this paper
• Exploring Network Structure with the Density of States

  2024cites this paper
• Dynamic Silos: Increased Modularity and Decreased Stability in Intraorganizational Communication Networks During the COVID-19 Pandemic

  2024cites this paper
• Recurrences reveal shared causal drivers of complex time series

  2023cites this paper
• Mining Statistically Significant Communities From Weighted Networks

  2023cites this paper
• On the Statistical Significance of a Community Structure

  2023influential citation
• Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection

  2023cites this paper
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar

  2023cites this paper
• Graph neural network inspired algorithm for unsupervised network community detection

  2022cites this paper
• Modeling the Interaction Networks about the Climate Change on Twitter: A Characterization of its Network Structure

  2022cites this paper
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection

  2022cites this paper
• Approximate Conditional Sampling for Pattern Detection in Weighted Networks

  2021cites this paper
• Resolution limit-free community detection reveals unique patterns of resting-state network connectivity in posttraumatic stress disorder: A PGC-ENIGMA PTSD Consortium investigation

  2021cites this paper
• Dynamic Silos: Increased Modularity in Intra-organizational Communication Networks during the Covid-19 Pandemic

  2021cites this paper
• Mining Online Social Networks: Deriving User Preferences through Node Embedding

  2021cites this paper
• An algorithm for network community structure determination by surprise

  2020cites this paper
• A survey of community detection methods in multilayer networks

  2020cites this paper
• Revealing dynamic communities in networks using genetic algorithm with merge and split operators

  2020cites this paper
• CoVeC: Coarse-grained vertex clustering for efficient community detection in sparse complex networks

  2020cites this paper
• Deep Domain Adaptation for Regression

  2020cites this paper
• Community detection in networks using bio-inspired optimization: Latest developments, new results and perspectives with a selection of recent meta-heuristics

  2020cites this paper
• Computing exact P-values for community detection

  2020cites this paper
• Efficient identification of multiple pathways: RNA-Seq analysis of livers from 56Fe ion irradiated mice

  2020cites this paper
• Resolution limit revisited: community detection using generalized modularity density

  2020cites this paper
• Community detection through vector-label propagation algorithms

  2020cites this paper
• An algorithm for network community structure detection by Surprise

  2019cites this paper
• Dynamic Partitioning of Evolving Graph Streams Using Nature-Inspired Heuristics

  2019cites this paper
• The community structure of functional brain networks exhibits scale-specific patterns of inter- and intra-subject variability

  2019cites this paper
• Combining bio-inspired meta-heuristics and novelty search for community detection over evolving graph streams

  2019cites this paper
• Generalized Markov stability of network communities

  2019cites this paper
• Detecting Statistically Significant Communities

  2018influential citation
• Método Rápido de Agrupamento de Vértices para Detecção de Comunidades em Redes Complexas de Larga-escala

  2018cites this paper
• Community structure: A comparative evaluation of community detection methods

  2018cites this paper
• The community structure of functional brain networks exhibits scale-specific patterns of variability across individuals and time

  2018cites this paper
• Analyzing Online Groups or the Communities in Social Media Networks by Algorithmic Approach

  2018cites this paper
• Global vs local modularity for network community detection

  2018influential citation
• Locally distributed spatial navigation in a scale-space model for grid cells

  2018cites this paper
• Community Detection in Weighted Directed Networks Using Nature-Inspired Heuristics

  2018cites this paper
• A local search method for graph clustering heuristics based on partitional Distribution learning

  2017cites this paper
• Détection de communautés orientée sommet pour des réseaux mobiles opportunistes sociaux. (Vertex centred community detection for opportunistic mobile social networks)

  2017cites this paper
• A semi-synchronous label propagation algorithm with constraints for community detection in complex networks

  2017cites this paper
• Online Social Networks:Measurements, Analysis and Solutions forMining Challenges

  2017cites this paper
• A layer reduction based community detection algorithm on multiplex networks

  2017cites this paper
• Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure

  2017cites this paper
• Network community detection using modularity density measures

  2017cites this paper
• A fusion condition for community detection with modularity 1 Chapter 1 A FUSION CONDITION FOR COMMUNITY DETECTION WITH MODULARITY

  2017cites this paper
• Community detection in weighted brain connectivity networks beyond the resolution limit

  2016cites this paper
• Metrics for Community Analysis

  2016cites this paper
• Community detection in graphs based on surprise maximization using firefly heuristics

  2016cites this paper
• Modular structure of brain functional networks: breaking the resolution limit by Surprise

  2016influential citation
• On the role of evangelism in consensus formation: a simulation approach

  2016cites this paper
• Quick Community Detection of Big Graph Data Using Modified Louvain Algorithm

  2016cites this paper
• Detecting Community Structure by Using a Constrained Label Propagation Algorithm

  2016cites this paper
• Conflict graph based Community Detection

  2016cites this paper
• Improved topic models for social media via community detection using user interaction and content similarity

  2016cites this paper
• Modular Brain Networks.

  2016cites this paper
• Network Analysis on Incomplete Structures

  2016influential citation
• Inverse Resolution Limit of Partition Density and Detecting Overlapping Communities by Link-Surprise

  2016cites this paper
• Engineering Graph Clustering Algorithms

  2015influential citation
• Detecting communities using asymptotical Surprise

  2015cites this paper
• A Multimodal Optimization and Surprise Based Consensus Community Detection Algorithm

  2015cites this paper
• Fast community structure local uncovering by independent vertex-centred process

  2015cites this paper
• Discovering Mesoscopic-level Structural Patterns on Social Networks: A Node-similarity Perspective

  2015cites this paper
• Identifying robust clusters and multi-community nodes by combining top-down and bottom-up approaches to clustering

  2015cites this paper
• How Many Political Parties Should Brazil Have? A Data-Driven Method to Assess and Reduce Fragmentation in Multi-Party Political Systems

  2015cites this paper
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering

  2015cites this paper
• How Many Political Parties Should Brazil Have? A Data-driven Method to Assess and Reduce Fragmentation in Multi-Party Political Systems

  2015cites this paper
• Link-Prediction Enhanced Consensus Clustering for Complex Networks

  2015cites this paper
• Community Detection in Signed Networks: the Role of Negative ties in Different Scales

  2015cites this paper
• Weighting dissimilarities to detect communities in networks

  2015cites this paper
• Finding Significant Resolutions

  2014cites this paper
• Algorithms and dynamical models for communities and reputation in social networks

  2014influential citation
• A Unified Model for Community Detection of Multiplex Networks

  2014cites this paper
• Clustering Evolving Networks

  2014cites this paper
• A detection of overlapping community in mobile social network

  2014cites this paper
• A Centrality Measure for Networks With Community Structure Based on a Generalization of the Owen Value

  2014influential citation
• A Flexible Fitness Function for Community Detection in Complex Networks

  2014cites this paper
• Cultural scene detection using reverse Louvain optimization

  2014cites this paper
• Detecting Communities Based on Network Topology

  2014cites this paper
• Genetic Algorithms for Multi-Objective Community Detection in Complex Networks

  2014cites this paper
• Algorithms for community and role detection in networks

  2014cites this paper
• Surprise maximization reveals the community structure of complex networks

  2013cites this paper
• Graph Clustering with Surprise: Complexity and Exact Solutions

  2013cites this paper
• Exploring the limits of community detection strategies in complex networks

  2013cites this paper
• Ants Crawling to Discover the Community Structure in Networks

  2013cites this paper
• Significant Scales in Community Structure

  2013cites this paper
• Identifying overlapping communities in complex networks with multimodal optimization

  2013cites this paper
• Analyzing complex functional brain networks: Fusing statistics and network science to understand the brain*†

  2013cites this paper
• Hidden Information Revealed by Optimal Community Structure from a Protein-Complex Bipartite Network Improves Protein Function Prediction

  2013cites this paper
• An incremental batch technique for community detection

  2013cites this paper
• Creating and analysing a social network built from clips of online news

  2013cites this paper
• Community Structure and Multi-Modal Oscillations in Complex Networks

  2013cites this paper
• A General Optimization Technique for High Quality Community Detection in Complex Networks

  2013cites this paper