Spectral K-way Ratio-cut Partitioning: Preliminary results, Part 1
University of California, Santa Cruz, Computer Research Laboratory, 1992 - Computer-aided design - 12 pages
Abstract: "Recent research on partitioning has focussed on the ratio-cut cost metric which maintains a balance between the sizes of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two- way ratio-cut partitioning have yielded higher quality partitioning results. In this paper we develop a spectral approach to multi-way ratio- cut partitioning which provides a generalization of the ratio-cut cost metric to k-way partitioning and a lower bound on this cost metric. Our approach uses Lanczos algorithm to find the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors are used to construct an orthogonal projection to map a vertex (of the graph) in an n-dimensional space into a k-dimensional subspace. We exploit the (near) orthogonality of the projected points to effect high quality clustering of points in a k-dimensional subspace. An efficient algorithm is presented for coercing the points in the k-dimensional subspace into k-partitions. Advancement over the current work is evidenced by the results of experiments on the standard MCNC benchmarks."
What people are saying - Write a review
We haven't found any reviews in the usual places.
ai;(via Barnes Board of Studies Computer Engineering consider an off-diagonal constraint cos(T/n cost(P degree(uh degree(v diagonal entry divided by V/|P edges between nodes edges cut eigenvalues of Q eigenvectors of Q g since node gives minus twice GP divided graph G Graph partitioning Hagen and Kahng Hence the off-diagonal heuristic i-1 The term Jason Zien k-dimensional subspace k-partition of G k-way partition K-Way Ratio-Cut Partitioning Laplacian lower bound Martine Schlag matriz of G n x k n x n matrix n-dimensional space nodes in partition non-zero exactly number of edges number of nodes number of partitions Observation off-diagonal entry optimal ratio-cut partition orthogonal projection orthonormal partition graph partition problem Proof ratio-cut cost metric ratioed assignment matriz ratioed partition matrix smallest eigenvalues smallest k eigenvalues Spectral K-Way Ratio-Cut total number twice the number unit-vectors University of California weighted quadratic displacement XXXai yja)(yih