|
Given N graphs, we need to make K classes of graphs based on structural similarity. Something, similar to Probabilistic Latent Semantic Analysis for text documents. Is there any good way to do this? |
|
An interesting way of doing it is using a graph kernel (for example, Fast Subtree Kernels on Graphs) and a kernel-based clustering algorithm (K-means can be adapted do work with kernels, as can spectral and graph clustering algorithms, see Dhillon et al, A unified view of kernel k-means, spectral clustering, and graph cuts, or Ng et al, Spectral Clustering: Analysis and an algorithm). Thanks Alexandre for throwing light on this topic :).
(Sep 16 '10 at 09:39)
Ashwin Kumar Kayyoor
+1 for Alexandre's answer. Didn't realize before replying that it was already answered. :)
(Sep 16 '10 at 09:46)
spinxl39
|
|
You would need a measure of similarity between objects which are graphs in your case, so you can use Vishwanathan et al, Graph kernels. Once the kernel is defined, you can use any kernel based clustering algorithm. Thanks a lot for the pointer, Spinx. I think that's almost exact what I was looking for. Will look at it.
(Sep 16 '10 at 09:47)
Ashwin Kumar Kayyoor
|
