Significant Scales in Community Structure

Abstract

Many complex networks show signs of modular structure, uncovered by community detection. Although many methods succeed in revealing various partitions, it remains difficult to detect at what scale some partition is significant. This problem shows foremost in multi-resolution methods. We here introduce an efficient method for scanning for resolutions in one such method. Additionally, we introduce the notion of "significance" of a partition, based on subgraph probabilities. Significance is independent of the exact method used, so could also be applied in other methods, and can be interpreted as the gain in encoding a graph by making use of a partition. Using significance, we can determine "good" resolution parameters, which we demonstrate on benchmark networks. Moreover, optimizing significance itself also shows excellent performance. We demonstrate our method on voting data from the European Parliament. Our analysis suggests the European Parliament has become increasingly ideologically divided and that nationality plays no role.

To appear in Scientific Reports

References in corpus (15)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Narrow scope for resolution-limit-free community detection
• Limited resolution in complex network community detection with Potts model approach
• The Geospatial Characteristics of a Social Movement Communication Network
• When are networks truly modular?
• Surprise maximization reveals the community structure of complex networks
• Resampling effects on significance analysis of network clustering and ranking

Cited by in corpus (26)

• Natural Scales in Geographical Patterns
• On community structure in complex networks: challenges and opportunities
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Faster unfolding of communities: speeding up the Louvain algorithm
• Detecting communities using asymptotical Surprise
• Estimating the resolution limit of the map equation in community detection
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Post-processing partitions to identify domains of modularity optimization
• Axioms for graph clustering quality functions
• On the evaluation potential of quality functions in community detection for different contexts
• Identifying multi-scale communities in networks by asymptotic surprise
• Community detection based on significance optimization in complex networks
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Generalized Markov stability of network communities
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• On the reliable and efficient numerical integration of the Kuramoto model and related dynamical systems on graphs
• A Statistical Density-Based Analysis of Graph Clustering Algorithm Performance
• Multiple Partitioning of Multiplex Signed Networks: Application to European Parliament Votes
• Detecting Statistically Significant Communities
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Metrics for Community Analysis: A Survey
• Community Integration Algorithms (CIAs) for Dynamical Systems on Networks
• Approximate Conditional Sampling for Pattern Detection in Weighted Networks
• Binomial Tails for Community Analysis