Robustness of community structure in networks

Abstract

The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining whether the structure found is statistically significant or whether, conversely, it could have arisen purely as a result of chance. In this paper we show that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure. We propose a suitable method for perturbing networks and a measure of the resulting change in community structure and use them to assess the significance of community structure in a variety of networks, both real and computer generated.

10 pages, 2 figures

References in corpus (30)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Natural Scales in Geographical Patterns
• Fast algorithm for detecting community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• The large-scale organization of metabolic networks
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Statistical Mechanics of Community Detection
• Community detection in complex networks using Extremal Optimization
• Parallel Tempering: Theory, Applications, and New Perspectives
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Clique percolation in random networks
• Finding Communities in Linear Time: A Physics Approach
• Size reduction of complex networks preserving modularity
• Community Detection as an Inference Problem
• Limited resolution in complex network community detection with Potts model approach
• Identifying "communities" within energy landscapes
• Structural Inference of Hierarchies in Networks
• Finding instabilities in the community structure of complex networks
• When are networks truly modular?
• Directed network modules
• Partitioning and modularity of graphs with arbitrary degree distribution
• Thermodynamics of Community Structure

Cited by in corpus (86)

• Community detection in graphs
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• The performance of modularity maximization in practical contexts
• Weight-conserving characterization of complex functional brain networks
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Mapping change in large networks
• Clustering and Community Detection in Directed Networks: A Survey
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Community Detection in Complex Networks Using Genetic Algorithms
• Multiresolution community detection for megascale networks by information-based replica correlations
• Robust network community detection using balanced propagation
• Community extraction for social networks
• LinkRank: Finding communities in directed networks
• Diffusion on networked systems is a question of time or structure
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Statistical significance of communities in networks
• Social significance of community structure: Statistical view
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• A Large-Scale Community Structure Analysis In Facebook
• Empirical Comparison of Algorithms for Network Community Detection
• Estimating network structure from unreliable measurements
• Propagation dynamics on networks featuring complex topologies
• Community Structure in the United Nations General Assembly
• Prioritizing network communities
• Measuring robustness of community structure in complex networks
• Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
• Exploring the solution landscape enables more reliable network community detection
• Multi-scale Modularity in Complex Networks
• Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
• Structure and Overlaps of Communities in Networks
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Online detection of temporal communities in evolving networks by estrangement confinement
• Measuring Significance of Community Structure in Complex Networks
• Uncovering allosteric pathways in caspase-1 with Markov transient analysis and multiscale community detection
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Measuring network resilience through connection patterns
• Significant communities in large sparse networks
• A generalised significance test for individual communities in networks
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Robustness of skeletons and salient features in networks
• Alternative approach to community detection in networks
• Closed benchmarks for network community structure characterization
• Core of communities in bipartite networks
• Spatial correlations in attribute communities
• Multiple Hybrid Phase Transition: Bootstrap Percolation on Complex Networks with Communities
• Communication and correlation among communities
• Confidence sets for network structure
• Inference for graphs and networks: Extending classical tools to modern data
• Robustness of community structure to node removal
• Non-parametric resampling of random walks for spectral network clustering
• Spectral coarse graining for random walk in bipartite networks
• Resampling effects on significance analysis of network clustering and ranking
• On the Permanence of Vertices in Network Communities
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Robustness modularity in complex networks
• Detecting the optimal number of communities in complex networks
• Robustness of community structure under edge addition
• Graph powering and spectral robustness
• Generalized network community detection
• Mask-GVAE: Blind Denoising Graphs via Partition
• Community detection for interaction networks
• Criterions for locally dense subgraphs
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Node-Context Network Clustering using PARAFAC Tensor Decomposition
• Identifying robust features of community structure in complex networks
• The art of community detection
• Characterizing functional brain networks and emotional centers based on Rasa theory of Indian aesthetics
• Multiplicity and Diversity: Analyzing the Optimal Solution Space of the Correlation Clustering Problem on Complete Signed Graphs
• Detecting Statistically Significant Communities
• The Atlas for the Aspiring Network Scientist
• Study Of The Fundamental Physical Principles in Atmospheric Modeling Based On Identification Of Atmosphere - Climate Control Factors: Bromine Explosion At The Polar Arctic Sunrise
• Ensembles based on the Rich-Club and how to use them to build soft-communities
• Long-time tails in sheared fluids
• Small-world of communities: communication and correlation of the meta-network
• Quantifying metadata relevance to network block structure using description length
• Vortical interactions in turbulent thermoacoustic systems
• Further insights into the interareal connectivity of a cortical network
• GA Based Q-Attack on Community Detection
• Validation of community robustness
• Measuring the Robustness of Graph Properties
• An Efficient homophilic model and Algorithms for Community Detection using Nash Dynamics
• Average Sensitivity of Spectral Clustering