Constant Approximation for Normalized Modularity and Associations Clustering
This addresses the challenge of efficiently approximating normalized clustering objectives in graph theory, offering a practical solution for applications in network analysis, though it is incremental in improving approximation guarantees.
The paper tackles the problem of graph clustering by introducing a broad class of objectives based on edge-to-vertex weight ratios, showing its relation to normalized modularity and associations, and provides a linear-time constant-approximation algorithm, achieving the first constant-factor approximations for these measures.
We study the problem of graph clustering under a broad class of objectives in which the quality of a cluster is defined based on the ratio between the number of edges in the cluster, and the total weight of vertices in the cluster. We show that our definition is closely related to popular clustering measures, namely normalized associations, which is a dual of the normalized cut objective, and normalized modularity. We give a linear time constant-approximate algorithm for our objective, which implies the first constant-factor approximation algorithms for normalized modularity and normalized associations.