IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1994 · 441 citations · 24 references
ComputingComputer ScienceComputational GeometryData MiningData StructuresData PartitioningDimensionality ReductionGraph AlgorithmsGraph TheorySpectral AnalysisSpectral MethodsGraph DecompositionsGraph PartitioningSpectral EmbeddingSpectral Graph AlgorithmsSpectral Graph Theory
Recent research on partitioning has focused on the ratio-cut cost metric, which maintains a balance between the cost 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 that provides a generalization of the ratio-cut cost metric to L-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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
24
Algorithms for clustering data
Bernhard Flury · Journal of Statistical Planning and Inference · 1989 · 6.5K citations
The Algebraic Eigenvalue Problem
E. I., J. H. Wilkinson · Mathematics of Computation · 1966 · 5.2K citations