The performance of modularity maximization in practical contexts

Abstract

Although widely used in practice, the behavior and accuracy of the popular module identification technique called modularity maximization is not well understood in practical contexts. Here, we present a broad characterization of its performance in such situations. First, we revisit and clarify the resolution limit phenomenon for modularity maximization. Second, we show that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum. Third, we derive the limiting behavior of the maximum modularity Q_max for one model of infinitely modular networks, showing that it depends strongly both on the size of the network and on the number of modules it contains. Finally, using three real-world metabolic networks as examples, we show that the degenerate solutions can fundamentally disagree on many, but not all, partition properties such as the composition of the largest modules and the distribution of module sizes. These results imply that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts. They also explain why many heuristics are often successful at finding high-scoring partitions in practice and why different heuristics can disagree on the modular structure of the same network. We conclude by discussing avenues for mitigating some of these behaviors, such as combining information from many degenerate solutions or using generative models.

20 pages, 14 figures, 6 appendices; code available at http://www.santafe.edu/~aaronc/modularity/

References in corpus (22)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Power-law distributions in empirical data
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• An information-theoretic framework for resolving community structure in complex networks
• Mixture models and exploratory analysis in networks
• Extracting the hierarchical organization of complex systems
• Analysis of the structure of complex networks at different resolution levels
• Robustness of community structure in networks
• Modularity-Maximizing Network Communities via Mathematical Programming
• A Bayesian Approach to Network Modularity
• Characterizing the dynamical importance of network nodes and links
• Evaluating Local Community Methods in Networks
• Identifying network communities with a high resolution
• Limited resolution in complex network community detection with Potts model approach
• When are networks truly modular?
• Hierarchy and Feedback in the Evolution of the E. coli Transcription Network
• Spectral tripartitioning of networks
• Detection of node group membership in networks with group overlap

Cited by in corpus (215)

• From Louvain to Leiden: guaranteeing well-connected communities
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Community detection in networks: A user guide
• Dynamic reconfiguration of human brain networks during learning
• Finding statistically significant communities in networks
• Controllability of Brain Networks
• Weight-conserving characterization of complex functional brain networks
• Consensus clustering in complex networks
• Finding overlapping communities in networks by label propagation
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Social Structure of Facebook Networks
• Random walks and diffusion on networks
• Limits of modularity maximization in community detection
• The ground truth about metadata and community detection in networks
• Robust Detection of Dynamic Community Structure in Networks
• Understanding brain networks and brain organization
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Structure and inference in annotated networks
• Narrow scope for resolution-limit-free community detection
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Uncovering space-independent communities in spatial networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Consistency and differences between centrality measures across distinct classes of networks
• Community Detection via Maximization of Modularity and Its Variants
• A Classification for Community Discovery Methods in Complex Networks
• Dynamic fluctuations coincide with periods of high and low modularity in resting-state functional brain networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Identifying the Community Structure of the International-Trade Multi Network
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• Network Analysis of Particles and Grains
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Efficiently inferring community structure in bipartite networks
• Multilayer Brain Networks
• The many facets of community detection in complex networks
• Mixing local and global information for community detection in large networks
• Community detection for correlation matrices
• Influence of Neighborhood SES on Functional Brain Network Development
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Estimating the number of communities in a network
• Extraction of Force-Chain Network Architecture in Granular Materials Using Community Detection
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• Choosing Wavelet Methods, Filters, and Lengths for Functional Brain Network Construction
• Multi-scale community organization of the human structural connectome and its relationship with resting-state functional connectivity
• Graph Unlearning
• The Influence of Network Topology on Sound Propagation in Granular Materials
• Network structure of inter-industry flows
• Bayesian stochastic blockmodeling
• Detecting communities using asymptotical Surprise
• Evolution of network architecture in a granular material under compression
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Spatial Guilds in the Serengeti Food Web Revealed by a Bayesian Group Model
• A Large-Scale Community Structure Analysis In Facebook
• Self-similar scaling of density in complex real-world networks
• Surprise maximization reveals the community structure of complex networks
• Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
• Z-score-based modularity for community detection in networks
• Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
• Multiway spectral community detection in networks
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Community structure of complex software systems: Analysis and applications
• Statistical inference of assortative community structures
• Assessing the consistency of community structure in complex networks
• Estimating the resolution limit of the map equation in community detection
• Resolving Structure in Human Brain Organization: Identifying Mesoscale Organization in Weighted Network Representations
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Streaming Graph Challenge: Stochastic Block Partition
• Community Structure in the United Nations General Assembly
• Fluctuations between high- and low-modularity topology in time-resolved functional connectivity
• Consistency of community structure in complex networks
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Detectability of communities in heterogeneous networks
• A New Metric for Quality of Network Community Structure
• Deep Community Detection
• 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
• Graph Clustering with Graph Neural Networks
• Using Triangles to Improve Community Detection in Directed Networks
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Using higher-order Markov models to reveal flow-based communities in networks
• Followers Are Not Enough: A Question-Oriented Approach to Community Detection in Online Social Networks
• Robust Detection of Hierarchical Communities from Escherichia coli Gene Expression Data
• Post-processing partitions to identify domains of modularity optimization
• Network structure, metadata and the prediction of missing nodes and annotations
• 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
• Online detection of temporal communities in evolving networks by estrangement confinement
• Revealing consensus and dissensus between network partitions
• Axioms for graph clustering quality functions
• Identifying communities by influence dynamics in social networks
• Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Fast and accurate determination of modularity and its effect size
• Adaptive Modularity Maximization via Edge Weighting Scheme
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Community Detection in Quantum Complex Networks
• Community consistency determines the stability transition window of power-grid nodes
• Extraction of hidden information by efficient community detection in networks
• Functional brain modules reconfigure at multiple scales across the human lifespan
• Different approaches to community detection
• Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• The inherent community structure of hyperbolic networks
• Community detection in directed acyclic graphs
• Revealing and exploiting hierarchical material structure through complex atomic networks
• Embedding-based Silhouette Community Detection
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Representative community divisions of networks
• Community evolution in retweet networks
• Improving the performance of algorithms to find communities in networks
• Combinatorial approach to Modularity
• Walk modularity and community structure in networks
• Enhancing community detection by local structural information
• Mesoscopic analysis of networks: applications to exploratory analysis and data clustering
• The emergent integrated network structure of scientific research
• Fast Detection of Community Structures using Graph Traversal in Social Networks
• Atmospheric reaction systems as null-models to identify structural traces of evolution in metabolism
• Core of communities in bipartite networks
• Gene communities in co-expression networks across different tissues
• Maximizing Barber's bipartite modularity is also hard
• Structure and inference in hypergraphs with node attributes
• Modularity and Projection of Bipartite Networks
• Discovering link communities in complex networks by exploiting link dynamics
• Network mutual information measures for graph similarity
• Comparative analysis on the selection of number of clusters in community detection
• Cluster analysis of weighted bipartite networks: a new copula-based approach
• Benefits of Bias: Towards Better Characterization of Network Sampling
• Community detection based on significance optimization in complex networks
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• On the Fourier transform of a quantitative trait: Implications for compressive sensing
• A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
• Graph coarse-graining reveals differences in the module-level structure of functional brain networks
• Dissociable changes in functional network topology underlie early category learning and development of automaticity
• Global disorder transition in the community structure of large-q Potts systems
• The stability to instability transition in the structure of large scale networks
• Identifying Correlation Clusters in Many-Body Localized Systems
• The landscape of NeuroImage-ing research
• Community structure revealed by phase locking
• Total variation based community detection using a nonlinear optimization approach
• On the Permanence of Vertices in Network Communities
• Multiresolution Consensus Clustering in Networks
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Latent Poisson models for networks with heterogeneous density
• Link community detection through global optimization and the inverse resolution limit of partition density
• Emergence and persistence of communities in coevolutionary networks
• Training Matters: Unlocking Potentials of Deeper Graph Convolutional Neural Networks
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Distributed Graph Clustering using Modularity and Map Equation
• GANC: Greedy Agglomerative Normalized Cut
• A hierarchy index for networks in the brain reveals a complex entangled organizational structure
• Topological Feature Based Classification
• Additive Approximation Algorithms for Modularity Maximization
• Mapping robust multiscale communities in chromosome contact networks
• Community structure in real-world networks from a non-parametrical synchronization-based dynamical approach
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Mining the modular structure of protein interaction networks
• Modelling community formation driven by the status of individual in a society
• Revealing evolutions in dynamical networks
• Grounding force-directed network layouts with latent space models
• Some remarks on modularity density
• Identifying robust features of community structure in complex networks
• Community Detection with the Map Equation and Infomap: Theory and Applications
• An algorithm for network community structure determination by surprise
• Obtaining Communities with a Fitness Growth Process
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Local multiresolution order in community detection
• Extending modularity by capturing the similarity attraction feature in the null model
• Stochastic Block Models are a Discrete Surface Tension
• A Statistical Density-Based Analysis of Graph Clustering Algorithm Performance
• Multiplicity and Diversity: Analyzing the Optimal Solution Space of the Correlation Clustering Problem on Complete Signed Graphs
• Uncovering migration systems through spatio-temporal tensor co-clustering
• Graph clustering with Boltzmann machines
• Vulnerable Connectivity Caused by Local Communities in Spatial Networks
• A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
• Stochastic fluctuations and the detectability limit of network communities
• Considerations about multistep community detection
• Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant
• Community detection by resistance distance: automation and benchmark testing
• Shaping Communities out of Triangles
• The Atlas for the Aspiring Network Scientist
• Mesoscopic architecture enhances communication across the Macaque connectome revealing structure-function correspondence in the brain
• Fast Super-Paramagnetic Clustering
• Diffusion in Networks With Overlapping Community Structure
• Network topology mapping of Chemical Compounds Space
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• Metrics for Community Analysis: A Survey
• Bad Communities with High Modularity
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Using social network graph analysis for interest detection
• Efficient Enumeration of the Optimal Solutions to the Correlation Clustering problem
• A new measure of modularity density for community detection
• Clustering evolving data using kernel-based methods
• Evaluation of Community Detection Methods
• Brain network modules of meaningful and meaningless objects
• Block-corrected Modularity for Community Detection
• Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
• Statistical mechanics of the minimum vertex cover problem in stochastic block models
• A framework for community detection in heterogeneous multi-relational networks
• Ensemble approach for generalized network dismantling
• Efficient discovery of multiple minimum action pathways using Gaussian process
• Network Controllability in the IFG Relates to Controlled Language Variability and Susceptibility to TMS
• Community membership consistency applied to corporate board interlock networks
• Modular Segregation of Structural Brain Networks Supports the Development of Executive Function in Youth
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach