  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.
