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.


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.


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.