The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
A min-max cut algorithm for graph partitioning and data clustering
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
An Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977
The Symmetric Eigenvalue Problem
Parlett, B. N. (1998) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971163 · Cited by 3,192
Partitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,684
Self-citationNew spectral methods for ratio cut partitioning and clustering
Hagen, L., & Kahng, A. B. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.159993 · Cited by 1,288
A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory
Fiedler, M. (1975) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1975.101357 · Cited by 1,042
Lower Bounds for the Partitioning of Graphs
Donath, W. E., & Hoffman, A. J. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.175.0420 · Cited by 660
Spectral partitioning works: planar graphs and finite element meshes
Spielman, D. A., & Teng, S.-H. (1996) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548468 · Cited by 393
Cited by
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
A Survey of Clustering Data Mining Techniques
Berkhin, P. (2006) · Grouping Multidimensional Data · doi:10.1007/3-540-28349-8_2 · Cited by 2,804
Document clustering based on non-negative matrix factorization
Xu, W., Liu, X., & Gong, Y. (2003) · Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval · doi:10.1145/860435.860485 · Cited by 1,860
Graph embedding techniques, applications, and performance: A survey
Goyal, P., & Ferrara, E. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.03.022 · Cited by 1,801
On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering
Ding, C., He, X., & Simon, H. D. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.70 · Cited by 985
Self-citation
Metadata
- Authors
- Ding, C. H. Q., He, X., Zha, H., Gu, M., & Simon, H. D.
- Venue
- Proceedings 2001 IEEE International Conference on Data Mining
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-14
- Pages
- 107-114
- ISSN
- 1550-4786 (ISSN-L)
- OpenAlex
- W2134737843
- Cited by
- 829
- References
- 16
- FWCI
- 15.22
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A min-max cut algorithm for graph partitioning and data clustering. https://app.cochat.ai/papers/10.1109/icdm.2001.989507
- The paper
- Ding, C. H. Q., He, X., Zha, H., Gu, M., & Simon, H. D. (2002). A min-max cut algorithm for graph partitioning and data clustering. Proceedings 2001 IEEE International Conference on Data Mining. https://doi.org/10.1109/icdm.2001.989507
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.