A min-max cut algorithm for graph partitioning and data clustering
Top Cited Papers
- 14 November 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 107-114
- https://doi.org/10.1109/icdm.2001.989507
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. 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. Theoretical analyses of min-max cut indicate that it leads to balanced partitions, and lower bonds are derived. The min-max cut algorithm is tested on news-group datasets and is found to outperform other current popular partitioning/clustering methods. The linkage-based 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 effectivepartition method.Keywords
This publication has 16 references indexed in Scilit:
- A spectral method to separate disconnected and nearly-disconnected web graph componentsPublished by Association for Computing Machinery (ACM) ,2001
- Bipartite graph partitioning and data clusteringPublished by Association for Computing Machinery (ACM) ,2001
- Approximation Algorithms for Clustering to Minimize the Sum of DiametersLecture Notes in Computer Science, 2000
- On the Quality of Spectral SeparatorsSIAM Journal on Matrix Analysis and Applications, 1998
- An improved spectral bisection algorithm and its application to dynamic load balancingParallel Computing, 1995
- New spectral methods for ratio cut partitioning and clusteringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- An improved two-way partitioning algorithm with stable performance (VLSI)IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Partitioning Sparse Matrices with Eigenvectors of GraphsSIAM Journal on Matrix Analysis and Applications, 1990
- Lower Bounds for the Partitioning of GraphsIBM Journal of Research and Development, 1973
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970