On Modularity Clustering

TLDR

Modularity is a recently introduced quality measure for graph clusterings that has attracted attention across disciplines, yet its properties remain poorly understood. The authors investigate the problem of finding clusterings that maximize modularity, aiming to establish theoretical foundations for prior and ongoing work using this metric. They prove the conjectured NP‑hardness of maximizing modularity in general and for cut‑restricted cases, present an integer linear programming formulation, and provide initial insights into the behavior and performance of the commonly used greedy agglomerative algorithm.

Abstract

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.