# Spectral Clustering: Laplacian vs Normalised Laplacian

I was looking at spectral clustering a graph. On looking at the Laplacian obtained, $L$ there does seem to be $5$ zero eigenvalues (rather eigenvalues close to 0 (i.e. $<0.01$)) and the sixth eigenvalue seems to be about $0.6$. So deciding that there must be $5$ clusters, I run spectral clustering.

However, different runs of spectral clustering (i.e picking the 5 smallest eigenvectors as columns, normalising them, and running k-means) seem to return quite different (not completely different though). Then I tried using the normalised Laplacian $D^{-0.5}LD^{-0.5}$, $D$ being the diagonal degree matrix of the graph, and the clusters obtained seem to be much more stable. Is there any explanation of this? Or is it that my code must have a bug (I did try checking for it.)

• k-means is a randomized algorithm and may find different local minima. – Anony-Mousse May 8 '15 at 6:42
• @Anony-Mousse : I agree. My observation was that the variation in the clusters was much lesser when using the normalised Laplacian rather than the Laplacian, and it is not clear why this should be the case. – Devil May 13 '15 at 0:29