Maximizing Modularity is hard

Abstract

Several algorithms have been proposed to compute partitions of networks into communities that score high on a graph clustering index called modularity. While publications on these algorithms typically contain experimental evaluations to emphasize the plausibility of results, none of these algorithms has been shown to actually compute optimal partitions. We here settle the unknown complexity status of modularity maximization by showing that the corresponding decision version is NP-complete in the strong sense. As a consequence, any efficient, i.e. polynomial-time, algorithm is only heuristic and yields suboptimal partitions on many instances.

10 pages, 1 figure

References in corpus (10)

• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Community detection in complex networks using Extremal Optimization
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Local modularity measure for network clusterizations
• An Information-Theoretic Approach to Network Modularity

Cited by in corpus (27)

• Critical phenomena in complex networks
• Hierarchical modularity in human brain functional networks
• The ground truth about metadata and community detection in networks
• Size reduction of complex networks preserving modularity
• Identifying network communities with a high resolution
• On community structure in complex networks: challenges and opportunities
• Communities, Knowledge Creation, and Information Diffusion
• Community Detecting By Signaling on Complex Networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Protein-Interaction-Networks: More than mere modules
• Graph Clustering with Graph Neural Networks
• A Real-Time Detecting Algorithm for Tracking Community Structure of Dynamic Networks
• Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
• The inherent community structure of hyperbolic networks
• DMCS : Density Modularity based Community Search
• Component models for large networks
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• A Game-Theoretic Approach for Detection of Overlapping Communities in Dynamic Complex Networks
• A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure Localization
• On Comparing and Enhancing Common Approaches to Network Community Detection
• Transfer Learning Based Multi-Objective Genetic Algorithm for Dynamic Community Detection
• Identification of community structure in networks with convex optimization
• Refining bridge-block decompositions through two-stage and recursive tree partitioning
• Gumbel-softmax Optimization: A Simple General Framework for Combinatorial Optimization Problems on Graphs
• Overlapping Communities in Complex Networks