|
I have been reading lots of papers on detecting community structure in graphs and general clustering algorithms. Many of them partition the graph using the second smallest eigenvector of the graph's laplacian. This apparently creates a normalized cut with lots of nice properties. It is not immediately apparent to me why this is the case. What is so special about the second smallest eigenvector? It seems so arbitrary. |
|
The choice isn't arbitrary. If you formalize the graph partitioning problem for two partitions (K=2), it leads to an eigenvalue problem. The Rayleigh-Ritz theorem says that the solution to this problem is precisely given by the eigenvector corresponding to the second smallest eigenvalue (the first eigenvalue actually happens to be zero in this case). For details, see section 5.1 of the spectral clustering tutorial by von Luxburg. Also the original Shi and Malik paper on Normalized cuts for image segmentation is a pain in the ass to read, but has the whole proof and some details: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.2324&rep=rep1&type=pdf
(Sep 25 '10 at 22:08)
Alexandre Passos ♦
What seems a bit more puzzling (but still makes sense) is that the other smallest eigenvectors also have meaning; the Ng, Jordan and Weiss paper does give a good intuition for that, however.
(Sep 25 '10 at 22:11)
Alexandre Passos ♦
spinxl39, thanks for the link!
(Sep 26 '10 at 03:38)
bijey
Alexandre, what Ng paper are you referring to?
(Sep 26 '10 at 07:19)
zaxtax ♦
Ng, Jordan and Weiss, Spectral Clustering: analysis and an algorithm http://www-2.cs.cmu.edu/Groups/NIPS/NIPS2001/papers/psgz/AA35.ps.gz
(Sep 26 '10 at 07:20)
Alexandre Passos ♦
|
