On Modularity Clustering

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.

• Publication year

  2008

• Venue

  IEEE Transactions on Knowledge and Data Engineering

• Publication date

  2008-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TKDE.2007.190689
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Network Analysis: Methodological Foundations

  2010cited by this paper
• Clustering

  2009influential reference
• Significance-Driven Graph Clustering

  2007cited by this paper
• Modularity and community structure in networks.

  2006cited by this paper
• Resolution limit in community detection

  2006cited by this paper
• On Modularity - NP-Completeness and Beyond

  2006cited by this paper
• Experiments on comparing graph clusterins

  2006cited by this paper
• Statistical mechanics of community detection.

  2006cited by this paper
• Spatially Constrained Networks and the Evolution of Modular Control Systems

  2006cited by this paper
• Comparing community structure identification

  2005cited by this paper
• Correlation clustering with a fixed number of clusters

  2005cited by this paper
• A Spectral Clustering Approach To Finding Communities in Graph

  2005cited by this paper
• Community detection in complex networks using extremal optimization.

  2005cited by this paper
• Local modularity measure for network clusterizations.

  2005cited by this paper
• Information-theoretic approach to network modularity.

  2004cited by this paper
• Analysis of weighted networks.

  2004cited by this paper
• Finding community structure in very large networks.

  2004cited by this paper
• Modularity from fluctuations in random graphs and complex networks.

  2004cited by this paper
• Fast algorithm for detecting community structure in networks.

  2003cited by this paper
• The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations

  2003cited by this paper
• Finding and evaluating community structure in networks.

  2003cited by this paper
• Mixing Patterns and Community Structure in Networks

  2002cited by this paper
• A clustering algorithm based on graph connectivity

  2000cited by this paper
• On clusterings-good, bad and spectral

  2000influential reference
• Data clustering: a review

  1999cited by this paper
• Recent directions in netlist partitioning: a survey

  1995cited by this paper
• Graph bisection algorithms with good average case behavior

  1984cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• An Information Flow Model for Conflict and Fission in Small Groups

  1977cited by this paper
• "PROOF"

  1934cited by this paper

• Capturing the Complexity of Bullying Perpetration and Victimisation: a Network Approach in a Representative Sample of Brazilian Adolescents

  2026cites this paper
• Formation of new start-ups: does business diversity in existing start-ups matter?

  2026cites this paper
• Dynamic Sensor Scheduling Based on Node Partitioning of Graphs

  2026cites this paper
• Selecting representative community partitions under modularity degeneracy: the STAR method

  2026influential citation
• Structural Clustering for Bipartite Graphs

  2026cites this paper
• A Multidisciplinary Perspective to Study the Film Trade Under a Digitally Transformed Industry: Bilateral Film Trade World (2000–2021)

  2026cites this paper
• Optimizing risk-based disease control strategies through network analysis: Case insights from FMD in Sri Lanka

  2026cites this paper
• Connectivity structure in fragmented forest areas in the Brazilian Amazon

  2026cites this paper
• A key process identification framework for aircraft assembly production based on the network with physical attributes

  2025cites this paper
• Simulation and Quantitative Analysis of Spatial Centromere Distribution Patterns

  2025cites this paper
• Vulnerable connectivity caused by local communities in spatial networks

  2025cites this paper
• Integrating transfer entropy and network analysis to explore social-ecological resilience evolution: a case study in South China Karst

  2025cites this paper
• Troika algorithm: approximate optimization for accurate clique partitioning and clustering of weighted networks

  2025influential citation
• Community-aware recommender system for personalized patient–physician matchmaking on bipartite graphs

  2025influential citation
• An Optimal Transport approach to model the community structure of the International Trade Network

  2025cites this paper
• Identifying coordination in online social networks through anomalous sharing behaviour

  2025cites this paper
• The Right to Hide: Masking Community Affiliation via Minimal Graph Rewiring

  2025cites this paper
• A multi-objective social-based algorithm for community detection

  2025cites this paper
• ν-LPA: Fast GPU-based Label Propagation Algorithm (LPA) for Community Detection

  2025cites this paper
• Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network

  2025cites this paper
• Discrete Ricci Flow for Detecting Gaps in Adiabatic Quantum Processes

  2025cites this paper
• The population history of Central Europe in the Early Bronze Age (2200/2100–1600/1500 BC) - a craniometric approach

  2025cites this paper
• Null-adjusted persistence function for high-resolution community detection

  2025influential citation
• Managing the fuzzy boundaries and partitions of marine ecological systems using network theory

  2025cites this paper
• Block-corrected Modularity for Community Detection

  2025cites this paper
• Proteomic biomarkers and biological pathways associated with atrial fibrillation in heart failure patients with reduced ejection fraction

  2025cites this paper
• Extensive Benchmarking of Community Detection Algorithms

  2025cites this paper
• New bounds on the modularity of $G(n,p)$

  2025cites this paper
• ONTraC characterizes spatially continuous variations of tissue microenvironment through niche trajectory analysis

  2025cites this paper
• ERPC: Efficient Rule Partitioning Through Community Detection for Packet Classification

  2025influential citation
• When Does the Silhouette Score Work? A Comprehensive Study in Network Clustering

  2025cites this paper
• The State and the Emergence of the First American Party System: Roll Call Voting in the New York State Assembly during the Early Republic

  2025cites this paper
• Scale invariance and statistical significance in complex weighted networks

  2025cites this paper
• Simple yet effective heuristic community detection with graph convolution network

  2025cites this paper
• ComVis: a four-level prompt model for overlapping community detection with graph visualization

  2025cites this paper
• Supervised network prediction for household statistics

  2025cites this paper
• A Novel Multiscale Graph Signal Processing and Network Dynamics Approach to Vibration Analysis for Stone Size Discrimination via Nonlinear Manifold Embeddings and a Convolutional Self-Attention Model

  2025cites this paper
• Towards Dynamic Community Detection with Leiden Algorithm

  2025cites this paper
• Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning

  2025cites this paper
• Evading Overlapping Community Detection via Proxy Node Injection

  2025influential citation
• A Parallel Hierarchical Approach for Community Detection on Large-scale Dynamic Networks

  2025cites this paper
• Quantile return connectedness of theme factors and portfolio implications: Evidence from the US and China

  2025cites this paper
• Contrast subgraphs catch patterns of altered functional connectivity in autism spectrum disorder

  2025cites this paper
• Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning

  2025cites this paper
• Community Detection in Energy Networks based on Energy Self-Sufficiency and Dynamic Flexibility Activation

  2025cites this paper
• From genomic discovery to application in age-related hearing loss: a global bibliometric and cross-ethnic analysis

  2025cites this paper
• Designing Parallel Algorithms for Community Detection using Arachne

  2025cites this paper
• MOUFLON: Multi-group Modularity-based Fairness-aware Community Detection

  2025cites this paper
• Approximating temporal modularity on graphs of small underlying treewidth

  2025cites this paper
• Complex network analysis of extreme temperature events in the Contiguous United States

  2025cites this paper
• Exploring the Computational Complexity of Uniform Random Sampling and SAT Counting with Phase Transitions

  2025cites this paper
• A general partitioning strategy for non-centralized control

  2025cites this paper
• Network-informed analysis of a multivariate trait-space reveals optimal trait selection

  2025cites this paper
• Dual temporal pathway model of emotion processing based on dynamic network reconfiguration analysis of EEG signals.

  2025cites this paper
• Modularity Based Community Detection in Hypergraphs

  2024cites this paper
• Improving modularity score of community detection using memetic algorithms

  2024cites this paper
• A Review of Community Detection Based on Modularity Optimization in Complex Networks

  2024cites this paper
• A multi-core periphery perspective: Ranking via relative centrality

  2024cites this paper
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection

  2024cites this paper
• A Study of The Market of Fat Ox and Corn in Bahia/Brazil Via Weighted Networks By Ρ_DCCA

  2024cites this paper
• Polarization-Affinity of Indonesian Political Figures: Insights from Network of Twitter Followers with Modularity Clustering and Linear Arrangement

  2024cites this paper
• Complex network community discovery using fast local move iterated greedy algorithm

  2024cites this paper
• A Dual Adaptive Assignment Approach for Robust Graph-Based Clustering

  2024cites this paper
• Evolutionary rewiring of the dynamic network underpinning allosteric epistasis in NS1 of influenza A virus

  2024cites this paper
• An Enhanced Bat Algorithm Using Clustering Coefficient for Community Detection in Complex Networks

  2024cites this paper
• A Network-Based Clustering Method to Ensure Homogeneity in Regional Frequency Analysis of Extreme Rainfall

  2024cites this paper
• Unveiling Market Trends in Pre-Owned Luxury Goods: An Approach Using Network Motifs for ROI Analysis

  2024cites this paper
• Linear clustering process on networks: a comparative study

  2024cites this paper
• Modularity aided consistent attributed graph clustering via coarsening

  2024cites this paper
• Evolución de la estructura de la economía colombiana a partir de la teoría de redes y detección de comunidades para el periodo 2005-2021

  2024cites this paper
• Coordinated Behavior in Information Operations on Twitter

  2024cites this paper
• Characterizing Spatially Continuous Variations in Tissue Microenvironment through Niche Trajectory Analysis

  2024cites this paper
• Strategies for improving the quality of community detection based on modularity optimization

  2024cites this paper
• Adaptive Local Modularity Learning for Efficient Multilayer Graph Clustering

  2024cites this paper
• Semantic network analysis in consumer and marketing research: application areas in phygital contexts

  2024cites this paper
• Detecting Urban Community Based on Urban Mobility Patterns From the Public Transportation Trip-Chain Data: A Case Study of Seoul, South Korea

  2024cites this paper
• Quality assessment and community detection methods for anonymized mobility data in the Italian Covid context

  2024cites this paper
• Interference Produces False-Positive Pricing Experiments

  2024cites this paper
• GSL-LPA: Fast Label Propagation Algorithm (LPA) for Community Detection with no Internally-Disconnected Communities

  2024cites this paper
• Uncovering Flat and Hierarchical Topics by Community Discovery on Word Co-occurrence Network

  2024cites this paper
• MEA-NAP compares microscale functional connectivity, topology, and network dynamics in organoid or monolayer neuronal cultures

  2024cites this paper
• Quantile volatility connectedness among themes and sectors: Novel evidence from China

  2024cites this paper
• Buffered Streaming Edge Partitioning

  2024cites this paper
• An Approach for Addressing Internally-Disconnected Communities in Louvain Algorithm

  2024cites this paper
• On Inference for Modularity Statistics in Structured Networks

  2024cites this paper
• An Evolutionary Algorithm With Heuristic Operator for Detecting Protein Complexes in Protein Interaction Networks With Negative Controls

  2024cites this paper
• Community Deception in Attributed Networks

  2024cites this paper
• Application of Social Network Analysis for Comparison and Ranking of Internet Service Providers

  2024cites this paper
• Sink-source connectivity for restocking of Pinna nobilis in the western Mediterranean Sea.

  2024cites this paper
• CSIM: A Fast Community Detection Algorithm Based on Structure Information Maximization

  2024cites this paper
• Using adjacency matrix to explore remarkable associations in big and small mineral data

  2024cites this paper
• DF Louvain: Fast Incrementally Expanding Approach for Community Detection on Dynamic Graphs

  2024cites this paper
• A Case Study Comparing Twitter Communities Detected by the Louvain and Leiden Algorithms During the 2022 War in Ukraine

  2024cites this paper
• Self-Adjusted Consensus Clustering with Agglomerate Algorithms

  2024cites this paper
• General Variable Neighborhood Search for the optimization of software quality

  2024cites this paper
• Multi-objective general variable neighborhood search for software maintainability optimization

  2024cites this paper
• Fuzzy clustering with Barber modularity regularization

  2024cites this paper
• MEA-NAP: A flexible network analysis pipeline for neuronal 2D and 3D organoid multielectrode recordings

  2024cites this paper
• Assessing climate vulnerability and nonlinear rainfall dynamics in complex networks

  2024influential citation
• RDSA: A Robust Deep Graph Clustering Framework via Dual Soft Assignment

  2024cites this paper