CODEWITHSUNDEEP
pythongraphcluster-analysis
Peyman
Peyman

Reputation: 3077

Graph clustering algorithm

the best way I can explain what I'm looking for is using this picture:

enter image description here

Obviously the visual aid makes it a lot easier for us to group these graphs but I would also think that finding dense sub-graphs should be a solvable problem using an algorithm. I tried MCL algorithm due to its popularity but it wouldn't work fine because it doesn't, seemingly at least, allow directional edges. I attempted to weight the edges differently but that didn't help the clustering process either. I'd like to find dense spots in the graph and I do have a way to verify that a given cluster is viable, there are cases where some elements just can't be together if that helps.

The output of that would be:

Cluster 0: A, B, C

Cluster 1: D, E, F, G

In this case if D is a suspicious element, using a different approach I can figure out which cluster in belongs to.

Upvotes: 1

Views: 1422

Answers (1)

Ray
Ray

Reputation: 176

This problem is a research area by itself (and part of my PhD thesis...) The best solution usually depends on your mathematical definition of "cluster" or "community". For example, you can minimize the number inter-cluster edges, which is called the graph partition problem.

Fortunato wrote a nice review paper on this topic: https://arxiv.org/pdf/0906.0612

My personal favorite, besides our own method, is the simulated annealing.

Upvotes: 1

Related Questions