Spectral k-way ratio-cut partitioning: Preliminary results, Part 1
Pak K. Chan, Martine Schlag, Jason Zien, University of California, Santa Cruz. Computer Research Laboratory
University of California, Santa Cruz, Computer Research Laboratory, 1992 - Computers - 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.
Barnes Board of Studies Computer Engineering consider an off-diagonal constraint cos(jr/n cost(V degree of ug degree(uh diagonal matrix divided by Pg edges between nodes edges cut eigenvalues of Q eigenvectors of Q entry of RTQ(G)R fc-partition fc-way partition g since node G-p divided ghth component ghth element gives minus twice graph G Graph partitioning gth diagonal entry Hagen and Kahng Hence the gth Hence the off-diagonal heuristic ijth j n n Jason Zien k-way Laplacian lower bound Martine Schlag matrix in Rfc n x k n x n matrix nodes in partition nodes in Pg non-zero exactly number of edges number of nodes number of partitions Observation off-diagonal entry orthogonal projection orthonormal partition graph partition Ph partition problem Pg and nodes Proof ratio-cut cost metric ratioed assignment matrix ratioed partition matrix smallest k eigenvalues twice the number unit-vectors weighted quadratic displacement YTQ(G)Y z i=i j=i