A min-max cut algorithm for graph partitioning and data clustering

By Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, Horst D. Simon. Proceedings 2001 IEEE International Conference on Data Mining, 2001

954 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/6ebb015ac7f7872ecadd75b837e859621abd0751

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Statistical and Nonlinear Physics

Citations in the corpus

Document clustering based on non-negative matrix factorization (2003, background): “Many criterion functions, such as the Average Cut [2], Average Association [11], Normalized Cut [11], Min-Max Cut [5], etc, have been proposed along with the eﬃcient algorithms for ﬁnding their optimal solutions.”
Document clustering using locality preserving indexing (2005, background): “Many criterion functions, such as the ratio cut [4], average association [23], normalized cut [23], and min-max cut [8] have been proposed along with the corresponding eigen-problem for finding their optimal solutions.”
A Multiobjective Genetic Algorithm to Find Communities in Complex Networks (2012, background): “It is worth noting that the Pareto-optimal solutions as outlined in [28] always include the optimal solutions of the clustering problems with a single objective to optimize.”
Ranking-based clustering of heterogeneous information networks with star network schema (2009, background): “Clustering on graphs, often called graph partition, aims at partitioning a given graph into a set of subgraphs based on different criteria, such as minimum cut, min-max cut [4] and normalized cut [14].”
Harvesting large-scale weakly-tagged image databases from the web (2010, methodology): “For a given image topic C, a graph is first constructed for organizing all its weakly-tagged images according to their visual similarity contexts [11-12], where each node on the graph is one weakly-tagged image for the given image topic C and an edge between two nodes is used to characterize the vis”
Deep Representation Learning for Social Network Analysis (2019, background): “For examples, (Shi and Malik, 2000) and (Ding et al., 2001) seek to maximize the number of connections within clusters while minimize the connections between clusters.”
A survey of graph theoretical approaches to image segmentation (2013, background): “The ratio cut [48] and MinMaxCut [49] define different cut functions on other types of data and lead to different graph Laplacians for clustering.”
Document clustering by concept factorization (2004, methodology): “In this paper, we will only consider partitional methods.”
A Formal Study of Shot Boundary Detection (2007, background): “Unfortunately, the problem is NP-complete because of its combinatory nature [55].”
Bots increase exposure to negative and inflammatory content in online social systems (2018, positive): “To determine the two underlying polarized groups, we look for a partition that minimizes inter-group interactions and use the Fiedler vector approach (24) for an efficient estimation (cf.”
On the spatial partitioning of urban transportation networks (2012, methodology): “Some algorithms of similar principles as Ncut may also be appropriate such as Min–Max Cut, which has a different objective function than Ncut but also seeks to minimize the intra-cluster variance and maximize the inter-cluster variance (Ding et al., 2001).”
Parallel Spectral Clustering in Distributed Systems (2011, background): “An example similarity function is the Gaussian: S ij ¼ exp À kx x x x i À x x x x j k 2 2 2”
On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering (2005, methodology): “the Ratio Cut [6], the Normalized Cut [13], and the MinMax Cut [4].”
Real-time automatic tag recommendation (2008, methodology): “The Min-Max Cut algorithm minimizes between-cluster sum of weights and maximizes the withincluster sum of weights [6].”
Local Modeling of Attributed Graphs: Algorithms and Applications (2016, methodology): “Widely used methods include METIS [68] and spectral clustering [39, 109], which aim to find a k-way partitioning of the graph.”