%0 Conference Paper %1 Chan1993Spectral %A Chan, Pak K %A Schlag, Martine D F %A Zien, Jason Y %B DAC '93 Proc. 30th Int. Conf. Des. Autom. %C New York, NY, USA %D 1993 %I ACM %K clustering graph phd schemdesc %P 749--754 %R http://dx.doi.org/10.1145/157485.165117 %T Spectral K-way ratio-cut partitioning and clustering %U http://dx.doi.org/10.1145/157485.165117 %X 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 multiway 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 involves finding the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors provide an embedding of the graph’s n vertices into a k-dimensional subspace. We devise a time and space efficient clustering heuristic to coerce the points in the embedding into k partitions. Advancement over the current work is evidenced by the results of experiments on the standard benchmarks. %@ 0-89791-577-1

@inproceedings{Chan1993Spectral, 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 multiway 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 involves finding the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors provide an embedding of the graph’s n vertices into a k-dimensional subspace. We devise a time and space efficient clustering heuristic to coerce the points in the embedding into k partitions. Advancement over the current work is evidenced by the results of experiments on the standard benchmarks.}, added-at = {2013-12-17T09:48:27.000+0100}, address = {New York, NY, USA}, author = {Chan, Pak K and Schlag, Martine D F and Zien, Jason Y}, biburl = {https://www.bibsonomy.org/bibtex/220763cf80034da784bd2e0982cf5f0c6/jullybobble}, booktitle = {DAC '93 Proc. 30th Int. Conf. Des. Autom.}, doi = {http://dx.doi.org/10.1145/157485.165117}, interhash = {6345f0858370841043e0c4235722c672}, intrahash = {20763cf80034da784bd2e0982cf5f0c6}, isbn = {0-89791-577-1}, keywords = {clustering graph phd schemdesc}, pages = {749--754}, publisher = {ACM}, timestamp = {2014-07-27T15:43:19.000+0200}, title = {{Spectral K-way ratio-cut partitioning and clustering}}, url = {http://dx.doi.org/10.1145/157485.165117}, year = 1993 }