Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
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]](https://i.stack.imgur.com/lideD.jpg)
Eigengap heuristic would suggest cluster number: 1. How should I choose number of clusters in this case ?
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.
