A min-max cut algorithm for graph partitioning and data clustering
Lists
Only you see this
Abstract
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. In this paper, we propose a new algorithm for graph partitioning 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 partitioning. Theoretical analyses of min-max cut indicate that it leads to balanced partitions, and lower bounds are derived. The min-max cut algorithm is tested on newsgroup data sets and is found to out-perform other current popular partitioning/clustering methods. The linkage-based refinements to the algorithm further improve the quality of clustering substantially. We also demonstrate that a linearized search order based on linkage differential is better than that based on the Fiedler vector, providing another effective partitioning method.
BibTeX
@inproceedings{ding2001min,
author = {Chris Ding and Xiaofeng He and Hongyuan Zha and Ming Gu and Horst D. Simon},
title = {{A min-max cut algorithm for graph partitioning and data clustering}},
booktitle = {ICDM},
year = {2001},
doi = {10.1109/icdm.2001.989507},
}Loading related content...