How do I choose number of clusters when Eigengap heuristic suggest 1 for spectral clustering?

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: [

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

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

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).