A wide range of clustering methods introduce a cost function whose minimal solution provides a clustering solution. \(K\) -means is a common cost function which is defined by the within-cluster sum of squared distances from the means [1]}. The data can be demonstrated by a graph, whose nodes represent the objects and the edge weights are the pairwise similarities between the objects. Then, a wide range of different graph partitioning methods can be applied to produce the clusters. Arguably, the most basic graph-based method is the Min Cut (Minimum \(K\) -Cut) cost function [2]}, [3]}, in which the goal is to partition the graph into exactly \(K\)  connected components (clusters) such that the sum of the inter-clusters edge weights is minimal. As we will see, the Min Cut cost function often yields separating singleton clusters, in particular when the clusters have diverse densities. To overcome such problem, several clustering methods normalize the Min Cut clusters to render more balanced clusters. For example, they propose to normalize the Min Cut clusters by the size of the clusters (Ratio Assoc [4]} and Ratio Cut [5]}) or the degree of the clusters (Normalized Cut [6]}).
