Limits of modularity maximization in community detection

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.

9 pages, 9 figures. Analysis extended to other global optimization methods. Final version published in Physical Review E

References in corpus (13)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Analysis of the structure of complex networks at different resolution levels
• Narrow scope for resolution-limit-free community detection
• When are networks truly modular?
• Partitioning and modularity of graphs with arbitrary degree distribution

Cited by in corpus (95)

• 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
• Network community detection using modularity density measures
• Multilevel Hierarchical Kernel Spectral Clustering for Real-Life Large Scale Complex Networks
• Information filtering via hybridization of similarity preferential diffusion processes
• Axioms for graph clustering quality functions
• Hierarchical Graph Clustering using Node Pair Sampling
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• 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
• A Bi-clustering Framework for Consensus Problems
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• On the Permanence of Vertices in Network Communities
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Emergence of Clustering in an Acquaintance Model without Homophily
• Detecting Communities in Complex Networks using an Adaptive Genetic Algorithm and node similarity-based encoding
• Static and Dynamic Aspects of Scientific Collaboration Networks
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Resolution Limits for Detecting Community Changes in Multilayer Networks
• Community detection in weighted brain connectivity networks beyond the resolution limit
• The Hyperspherical Geometry of Community Detection: Modularity as a Distance
• Modelling community formation driven by the status of individual in a society
• Mining the modular structure of protein interaction networks
• Convex Relaxation Methods for Community Detection
• Identifying robust features of community structure in complex networks
• Extending modularity by capturing the similarity attraction feature in the null model
• Local multiresolution order in community detection
• Obtaining Communities with a Fitness Growth Process
• Meet me in the middle: The reunification of Germany's research network
• On the modularity of 3-regular random graphs and random graphs with given degree sequences
• AOC; Assembling Overlapping Communities
• Uncovering migration systems through spatio-temporal tensor co-clustering
• The Atlas for the Aspiring Network Scientist
• Comprehensive spectral approach for community structure analysis on complex networks
• On Efficiently Detecting Overlapping Communities over Distributed Dynamic Graphs
• Towards a robust algorithm to determine topological domains from colocalization data
• Resolution limit revisited: community detection using generalized modularity density
• Router-level community structure of the Internet Autonomous Systems
• Botnet Detection using Social Graph Analysis
• Metrics for Community Analysis: A Survey
• The parameterised complexity of computing the maximum modularity of a graph
• Clique-based Method for Social Network Clustering
• Evaluation of Community Detection Methods
• A new measure of modularity density for community detection
• Topic-based Community Search over Spatial-Social Networks (Technical Report)
• Vortical interactions in turbulent thermoacoustic systems
• Clustering evolving data using kernel-based methods
• Network community detection via iterative edge removal in a flocking-like system
• Laplacian Mixture Modeling for Network Analysis and Unsupervised Learning on Graphs
• SCG: Spotting Coordinated Groups in Social Media
• Modularity of Erdős-Rényi random graphs
• A framework for community detection in heterogeneous multi-relational networks
• Modularity of regular and treelike graphs
• Correlation-Based Community Detection
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach