Clustering Methods Based on Minimum-Cut Trees

In this paper we introduce a simple clustering method for undirected graphs. The clustering method uses maximum ow techniques on the link-structure of the graph. The quality of the produced clusters is bounded by strong minimum-cut and expansion criteria. We also present a framework for hierarchical clustering and apply it to real-world data. We conclude that the clustering algorithms satisfy strong theoretical criteria and perform well in practice