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

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Functional cartography of complex metabolic networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• 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
• High-resolution measurements of face-to-face contact patterns in a primary school
• Social Structure of Facebook Networks
• Limits of modularity maximization in community detection
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Narrow scope for resolution-limit-free community detection
• Multiresolution community detection for megascale networks by information-based replica correlations
• Assessing the relevance of node features for network structure
• Limited resolution in complex network community detection with Potts model approach
• The Geospatial Characteristics of a Social Movement Communication Network
• Statistical significance of communities in networks
• Sex differences in intimate relationships
• When are networks truly modular?
• Deciphering Network Community Structure by Surprise
• Surprise maximization reveals the community structure of complex networks
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Significant communities in large sparse 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