Clustering with r-regular graphs

Abstract

In this paper, we present a novel graph-based clustering method, where we decompose a (neighborhood) graph into (disjoint) r-regular graphs followed by further refinement through optimizing the normalized cluster utility. We solve the r-regular graph decomposition using a linear programming. However, this simple decomposition suffers from inconsistent edges if clusters are not well separated. We optimize the normalized cluster utility in order to eliminate inconsistent edges or to merge similar clusters into a group within the principle of minimal K-cut. The method is especially useful in the presence of noise and outliers. Moreover, the method detects the number of clusters within a pre-specified range. Numerical experiments with synthetic and UCI data sets, confirm the useful behavior of the method. (C) 2008 Elsevier Ltd. All rights reserved.