Constant Approximation for Normalized Modularity and Associations Clustering
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 5 of its 23 references that are in the map. First posted on arXiv 29 Dec 2022.
Builds on
5 of 23 references.
References · 5
- 2022Correlation Clustering with Sherali-Adamscited by 15
- 2021Scalable Community Detection via Parallel Correlation Clusteringcited by 9
- 2016Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limitscited by 7
- 2015Relations Between Adjacency and Modularity Graph Partitioningcited by 2
- 2021Refining bridge-block decompositions through two-stage and recursive tree partitioningcited by 2
Built on by
Not cited yet.