Graph clustering algorithm

Question

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

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.

How do the edge directions relate to the clustering decisions? If you remove the directionality and have mere double-edges between nodes, than about any graph clustering algorithm will find that single cut point. BTW, a search on "graph cluster cut" should get you a lot of references. — Prune
– Prune, Commented Feb 14, 2018 at 1:23
I can easily get rid of the directions, they're not important, I didn't really need to add them. The fact that some of them have double edges is what's important. I tried the MCL algorithm and it couldn't cluster them out. I used a single edge with weight 2 for the double edges and 1 for the single edges. I got no luck. Is that kind of where you were heading? — Peyman
– Peyman, Commented Feb 14, 2018 at 17:58
Can you please clarify your question? I'm no longer sure what you want. You're not looking for us to debug your algorithm: you would have posted an MCVE. You're not considering other algorithms: you would have tried one of your search hits or @Ray's pointers by now. — Prune
– Prune, Commented Feb 14, 2018 at 20:04
No I'm going to do that but I just want to understand what you meant by your original comment. — Peyman
– Peyman, Commented Feb 14, 2018 at 23:06

Ray · Accepted Answer · 2018-02-14 01:25:51Z

1

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.

answered Feb 14, 2018 at 1:25

Ray

1761 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Peyman Over a year ago

Great tip, thanks. I'm reading the community detection in graphs paper. It's quite dense but it seems like it's doing exactly what I'm after.

Collectives™ on Stack Overflow

Graph clustering algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related