Spectral clustering of graph

Question

I am trying to cluster a graph using spectral clustering. However I am unaware of the number of classes that exist in the data. Would it be a good idea to apply PCA on the adjacency matrix of the graph to find the actual number of clusters in the data set? Are there any other options?

Answer 1

The problem of finding the correct number of classes is unsolved and there are many approaches that deal with this problem. For general approaches, you can have a look at the problem of finding k in a k-means.

When performing spectral analysis, you can use the eigengap method to find a good approximation of the number of classes. It consists in computing the differences between the consecutive ordered eigenvalues of the graph Laplacian.

If the difference between say, the 4th and the 5th eigenvalues is large compared to the other differences, then it is likely that there will be 4 classes in the graph. Note however that there is no perfect method to say whether a difference is large enough or not. In particular, just considering the largest difference might not lead to the best partition.

A common technique is to consider several numbers of classes and perform several k-means (or any other clustering). Then, keep the partition having the highest quality according to some external measure.

Answer 2

If you're using R or Python (or even C), you can have a look at the excellent igraph package. Especially, look at the various community detection algorithms that this package implements. What you discuss is closely related to the leading eigenvector algorithm of Newman (2006). Here is the paper introducing this algorithm, it is a very interesting read.

A good strategy is to implement several community detection algorithms and aggregate the results. This leads to algorithm-independent, more stable and significant results. Here is a link to a function that I wrote for that purpose. One "external measure" (as mentioned by P.-N. Mougel above) that you can use is the modularity.