Eigengap heuristic Method suggest number of clusters k is usually given by the value of k that maximizes the eigengap (difference between consecutive eigenvalues). I plotted the Eigenvalue distribution for my Data: [Ranked Eigenvalue]

Eigengap heuristic would suggest cluster number: 1. How should I choose number of clusters in this case ?

  • $\begingroup$ Isn't the first eigenvalue supposed to be 0? One 0 for each connected component? $\endgroup$ – Has QUIT--Anony-Mousse Dec 3 '17 at 0:36

The first eigenvalue in your plot is non-zero, whereas the last is one.

This seems to suggest that the Laplacian whose eigenvalues you are computing is different from the standard Laplacian $ L = D - W$, where $D$ is the matrix whose diagonal entries are degrees of nodes and $W$ is the weighted adjacency matrix. So in your plot, $\lambda_{19} = 1$ and $\lambda_{18} \neq 1$ but is $\approx 1$ which is indicative of the graph being one connected component.

So the correct way to interpret your plot would be to invert it ($\lambda \mapsto 1 - \lambda$) and then arrange them in increasing order, or to arrange them in decreasing order as-is.

Then you can use the eigengap heuristic to choose a suitable value for the number of clusters (7 seems to be a good choice as $\lambda_{13}-\lambda_{12}$ is large compared to $\lambda_{14}-\lambda_{13}$, or maybe 3 if the number of clusters is a constraint).

This is described in greater detail in Luxborg's excellent tutorial on Spectral Clustering, and you can find a footnote in Ng et al's seminal paper on the same.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.