Limits of modularity maximization in community detection
arXiv:1107.1155 · doi:10.1103/PhysRevE.84.066122
Abstract
Modularity maximization is the most popular technique for the detection of community structure in graphs. The resolution limit of the method is supposedly solvable with the introduction of modified versions of the measure, with tunable resolution parameters. We show that multiresolution modularity suffers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high. In benchmark networks with heterogeneous distributions of cluster sizes, the simultaneous elimination of both biases is not possible and multiresolution modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter. This holds for other multiresolution techniques and it is likely to be a general problem of methods based on global optimization.
arXiv comment9 pages, 9 figures. Analysis extended to other global optimization methods. Final version published in Physical Review E
References in corpus (27)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Maps of random walks on complex networks reveal community structure
- Evolution of networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Defining and identifying communities in networks
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Analysis of the structure of complex networks at different resolution levels
- Narrow scope for resolution-limit-free community detection
- Assessing the relevance of node features for network structure
- Local resolution-limit-free Potts model for community detection
- Statistical significance of communities in networks
- When are networks truly modular?
- Partitioning and modularity of graphs with arbitrary degree distribution
Cited by in corpus (96)
- Community detection in networks: A user guide
- Networks beyond pairwise interactions: structure and dynamics
- Consensus clustering in complex networks
- Detecting modules in quantitative bipartite networks: the QuaBiMo algorithm
- Community Detection via Maximization of Modularity and Its Variants
- A network approach to topic models
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- A Review of Stochastic Block Models and Extensions for Graph Clustering
- On community structure in complex networks: challenges and opportunities
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- The many facets of community detection in complex networks
- Significant Scales in Community Structure
- Faster unfolding of communities: speeding up the Louvain algorithm
- Detecting communities using asymptotical Surprise
- Surprise maximization reveals the community structure of complex networks
- Z-score-based modularity for community detection in networks
- Enhanced detectability of community structure in multilayer networks through layer aggregation
- Clustering via Hypergraph Modularity
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- Statistical inference of assortative community structures
- Exploring the limits of community detection strategies in complex networks
- Estimating the resolution limit of the map equation in community detection
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Streaming Graph Challenge: Stochastic Block Partition
- Hierarchical multiresolution method to overcome the resolution limit in complex networks
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- A New Metric for Quality of Network Community Structure
- Multiscale dynamical embeddings of complex networks
- Mesoscopic analysis of online social networks - The role of negative ties
- Limitation of multi-resolution methods in community detection
- Multilevel Hierarchical Kernel Spectral Clustering for Real-Life Large Scale Complex Networks
- Network community detection using modularity density measures
- Axioms for graph clustering quality functions
- Information filtering via hybridization of similarity preferential diffusion processes
- Multi-resolution community detection based on generalized self-loop rescaling strategy
- Hierarchical Graph Clustering using Node Pair Sampling
- Finding network communities using modularity density
- Community consistency determines the stability transition window of power-grid nodes
- Functional brain modules reconfigure at multiple scales across the human lifespan
- Different approaches to community detection
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- Community detection in networks via nonlinear modularity eigenvectors
- Core of communities in bipartite networks
- Identifying multi-scale communities in networks by asymptotic surprise
- Identifying hidden coalitions in the US House of Representatives by optimally partitioning signed networks based on generalized balance
- Discovering link communities in complex networks by exploiting link dynamics
- Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
- Asymptotic resolution bounds of generalized modularity and multi-scale community detection
- A Bi-clustering Framework for Consensus Problems
- Global disorder transition in the community structure of large-q Potts systems
- The stability to instability transition in the structure of large scale networks
- On the Permanence of Vertices in Network Communities
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Detecting Communities in Complex Networks using an Adaptive Genetic Algorithm and node similarity-based encoding
- Emergence of Clustering in an Acquaintance Model without Homophily
- Static and Dynamic Aspects of Scientific Collaboration Networks
- Resolution Limits for Detecting Community Changes in Multilayer Networks
- Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- Mining the modular structure of protein interaction networks
- The Hyperspherical Geometry of Community Detection: Modularity as a Distance
- Convex Relaxation Methods for Community Detection
- Community detection in weighted brain connectivity networks beyond the resolution limit
- Modelling community formation driven by the status of individual in a society
- Extending modularity by capturing the similarity attraction feature in the null model
- Obtaining Communities with a Fitness Growth Process
- Local multiresolution order in community detection
- Identifying robust features of community structure in complex networks
- Uncovering migration systems through spatio-temporal tensor co-clustering
- AOC; Assembling Overlapping Communities
- On the modularity of 3-regular random graphs and random graphs with given degree sequences
- Meet me in the middle: The reunification of Germany's research network
- Towards a robust algorithm to determine topological domains from colocalization data
- The Atlas for the Aspiring Network Scientist
- On Efficiently Detecting Overlapping Communities over Distributed Dynamic Graphs
- Comprehensive spectral approach for community structure analysis on complex networks
- Resolution limit revisited: community detection using generalized modularity density
- Router-level community structure of the Internet Autonomous Systems
- Botnet Detection using Social Graph Analysis
- The parameterised complexity of computing the maximum modularity of a graph
- Metrics for Community Analysis: A Survey
- Topic-based Community Search over Spatial-Social Networks (Technical Report)
- Vortical interactions in turbulent thermoacoustic systems
- Evaluation of Community Detection Methods
- Clique-based Method for Social Network Clustering
- Clustering evolving data using kernel-based methods
- A new measure of modularity density for community detection
- Network community detection via iterative edge removal in a flocking-like system
- Laplacian Mixture Modeling for Network Analysis and Unsupervised Learning on Graphs
- Leaders, Followers, and Community Detection
- Modularity of regular and treelike graphs
- Modularity of Erdős-Rényi random graphs
- SCG: Spotting Coordinated Groups in Social Media
- Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach
- Correlation-Based Community Detection
- A framework for community detection in heterogeneous multi-relational networks