Spectral min-max cut for graph partitioning and data clustering
Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, Horst D. Simon · eScholarship (California Digital Library) · 2001
An important application of graph partitioning is data clustering using a graph model -the pairwise similarities between all data objects form a weighted graph adjacency matrix that contains all necessary information for clustering.Here we propose a new algorithm for graph partition with an objective function that follows the min-:-max clustering principle.The relaxed version of the optimization of the min-max cut objective function leads to the Fiedler vector in spectral graph partition.The min-max cut algorithm is tested on newsgroup datasets and is found to outperform other current popular partitioning/ clustering methods.The linkagebased refinements in the algorithm further improve the quality of Clustering substantially.We also demonstrate that the linearized search order based on linkage differential is better than that based on the Fiedler vector, providing another effective partition method.