I'd like to cluster a graph in python using spectral clustering.
Spectral clustering is a more general technique which can be applied not only to graphs, but also images, or any sort of data, however, it's considered an exceptional graph clustering technique. Sadly, I can't find examples of spectral clustering graphs in python online.
Scikit Learn has two spectral clustering methods documented: SpectralClustering and spectral_clustering which seem like they're not aliases.
Both of those methods mention that they could be used on graphs, but do not offer specific instructions. Neither does the user guide. I've asked for such an example from the developers, but they're overworked and haven't gotten to it.
A good network to document this against is the Karate Club Network. It's included as a method in networkx.
I'd love some direction in how to go about this. If someone can help me figure it out, I can add the documentation to scikit learn.
Without much experience with Spectral-clustering and just going by the docs (skip to the end for the results!):
Code:
Output:
The general idea:
Introduction on the data and task from here:
Using sklearn & spectral-clustering to tackle this:
This describes normalized graph cuts as:
Sounds alright. So we create the adjacency matrix (
nx.to_numpy_matrix(G)
) and set the paramaffinity
to precomputed (as our adjancency-matrix is our precomputed similarity-measure).Edit: While unfamiliar with this, i looked for parameters to tune and found assign_labels:
So trying the less sensitive approach:
Output:
That's a pretty much perfect fit to the ground-truth!