CODEWITHSUNDEEP
cluster-analysissimilaritydirected-graph
Samuel Bushi
Samuel Bushi

Reputation: 341

Compare similarity between graphs?

I have multiple Concept Maps that are represented as directed graphs. I have used this method, to compare 2 concept maps, but now I'd like to classify / cluster similar graphs together.

AFAIK, the traditional clustering algorithm take input as multi-dimensional data points. But I've also read that it is difficult and not recommended to transform a graph into a vector.

In that case, How do I approach this problem?

Upvotes: 0

Views: 301

Answers (1)

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77485

Many (most, except for e.g. k-means, EM and Mean-shift) clustering algorithms use distances, not points.

For small data sets, hierarchical clustering is certainly the first method to try. Single-link, complete-link, average-link have little formal requirements, i.e. they may be used either with a distance or a similarity, which does not need to satisfy the triangle inequality. Other metrics such as Ward and centroid linkage require squared Euclidean distances and will probably not work here.

  1. compute pairwise graph matching distances
  2. check for any normalization (e.g. graph size) required
  3. run hierarchical clustering
  4. study the dendrogram, you may need to go back and improve your normalization, distance, etc.
  5. cut subtree clusters from the dendrogram

Upvotes: 0

Related Questions