The step of finding the minimum cut on graph G is a subroutine that can be implemented using different algorithms for this problem.
f(n, m) is the time complexity of computing a minimum cut in a graph with n vertices and m edges, and N is the number of clusters found.
For fast algorithms for finding a minimum cut in an unweighted graph: The clusters produced by the HCS clustering algorithm possess several properties, which can demonstrate the homogeneity and separation of the solution.
If G has a vertex x with degree <= n/2, then G has a minimum cut (that isolates x) with edges <= n/2, so G is not highly connected.
There is a famous theorem in graph theory that says that if every vertex has degree >= n/2, then the diameter of G (the longest path between any two nodes) <= 2.
Therefore, the number of edges in a highly connected graph must be at least (n × n/2)/2, where we sum the degrees of each vertex and divide by 2.
Alternatively, a refinement of the algorithm can first remove all vertices with a degree lower than certain threshold.