A Clustering Algorithm based on Graph Connectivity

We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. A similarity graph is defined and clusters in that graph correspond to highly connected subgraphs. A polynomial algorithm to compute them efficiently is presented. Our algorithm produces a solution with some provably good properties and performs well on simulated and real data. Keywords: Algorithms, Clustering, Minimum cut, Graph connectivity, diameter. 1 Introduction Problem definition: Cluster analysis seeks grouping of elements into subsets based on similarity between pairs of elements. The goal is to find disjoint subsets, called clusters, such that two criteria are satisfied: homogeneity: elements in the same cluster are highly similar to each other; and separation: elements in different clusters have low similarity to each other. The process of generating the subsets is called clustering. The similarity level is usually determined by a set of features of each element. Thes..