# Constant Approximation for Normalized Modularity and Associations Clustering

arXiv: https://arxiv.org/abs/2212.14334 · HTML: https://mlsanity.com/paper/2212.14334/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 29 Dec 2022.

## Builds on (most cited first, 5 of 5)

- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits](https://mlsanity.com/paper/1602.01016/) (2016)
- [Relations Between Adjacency and Modularity Graph Partitioning](https://mlsanity.com/paper/1505.03481/) (2015)
- [Refining bridge-block decompositions through two-stage and recursive tree partitioning](https://mlsanity.com/paper/2110.06998/) (2021)

## Abstract (arXiv)

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.