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.