Thursday, July 30, 2009

Spectral Graph Partitioning

There are a number of methods in the family of Spectral Graph Partitioning, including the traditional min-cut and various balanced cut criteria (such as ratio-cut, average-cut, normalized-cut and minmax-cut). Each method uses a different objective function and consequently a different definition of partition (cluster) indicator vector. The following two tutorials on Spectral Clustering both contain a good summary of these methods.
[1] Spectral Clustering, ICML 2004 Tutorial by Chris Ding
[2] A Tutorial on Spectral Clustering by Ulrike von Luxburg