1
$\begingroup$

I was using Markov Clustering to cluster nodes in my bidirectional graph, and overall the results were great. However, there were a couple instances where a weakly connected node would attract a node that's much more strongly connected to other nodes. So, for instance (this is a bit contrived, but it gets the point across) if I have a strongly connected clique of A,B,C,D, and a small offshoot between A and E the Markov algorithm may cluster B,C,D together and A and E together, because E is connected 100% to D.

A--[weight:10]--B
A--[weight:10]--C
A--[weight:10]--D
B--[weight:10]--C
B--[weight:10]--D
C--[weight:10]--D
A--[weight:1]--E

I'd prefer A,B,C, and D to be clustered together at minimum. Are there any known techniques for adjusting the probability matrix to account for this? Or is there a better algorithm? I like Markov Clustering because it uses a probability matrix which takes into account the weight of each connection, but in this instance it's problematic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.