2

Which methods is available for graph clustering? The most information by query "Graph clustering" concentrated on the finding set of nodes in the one large graph (or graph partition), but it isn't my case. But I interested in classical clustering task: I have a set of graphs, and I'd like to group this graphs in groups.

Which methods are available for this task?

I already read about graph embeddings, but this is comparatively new approach, and I think, that exists another approaches.

In particular, I have a set of trees with different structure, and I'd like to separate them into groups.

gung - Reinstate Monica
  • 145,122
Simplex
  • 171
  • Without knowing more about the problem, it might be the case that Synthetic Network Fusion may be appropriate. – Demetri Pananos Dec 24 '18 at 09:13
  • Thank you, I add information about specific: I have a set of trees with different structure, and I'd like to separate them into groups. – Simplex Dec 24 '18 at 09:17
  • Seems like it's not graph clustering, the techniques I know in graph clustering evolve around splitting a graph in groups of nodes that have some similarities. – Matthieu Brucher Dec 24 '18 at 09:25

2 Answers2

1

Many clustering algorithms (not k-means though) are agnostic to their input data type. All they need is a distance function.

So once you defined a distance function to quantify the similarity of your trees, then you can compute the distance matrix and use, e.g., HAC, PAM, DBSCAN, affinity propagation, spectral clustering, ...

Now graphs in different domains tend to require very different similarity measures, and these can be very problematic. For example, protein similarities...

Has QUIT--Anony-Mousse
  • 42,358
1
  1. I would use a whole graph embedding technique to map the graphs into Euclidean spaces.
  2. Use traditional clustering techniques.

For the 1st step this package this might help:

https://karateclub.readthedocs.io/

Ben Rozemberczki
  • 31