Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I had a really huge sets of molecules and it's I'd like to compare according to various factors. So I created a similarity measure which was very informative and fitted for comparing different types of molecules. After I introduced comparing between two elements I'd like to go further and try to cluster them, however I've got a problem, my similarity measure is not reflexive, i.e. $dist(A,B)!=dist(B,A)$ (though it satisfies triangle inequality). And I have no problem about it since it represents the problem of my interest perfectly. I generated the distance matrix ( or dissimilarity, my measure is bounded $[0,1]$ so it could be converted to similarity as well ).

I thought that clustering with asymmetric distances isn't common thing, so there is not much algorithms implemented (only ones that I know are OPTICS and DBSCAN, but as I tried they are no good), so I decided maybe I should change this problem to the problem of clustering strongly connected directed graph with weights. Maybe someone is aware of such issue and knows some usable implementation of it?

I found Tarjan's article, so maybe someone is familiar with the approach described there and knows possible implementation.

This question is also methodological. Maybe I should check another clustering algorithms, however I don't want to change my measure formula.

share|cite|improve this question
Checking if a distance function satisfies triangle inequality may be useful too... – DVD May 13 '13 at 22:02
Thank you, I forgot to mention. My distance function satisfies triangle inequality. – user974514 May 13 '13 at 22:24
I'm interested in a solution to this. Have you figured out something yet. – yati sagade Sep 29 '14 at 10:05

You can check the Knowledge Discovery Toolbox (KDT) here (a link to a related paper: A Flexible Open-Source Toolbox for Scalable Complex Graph Analysis). Also, take a look at this article: Preconditioners Based on Strong Subgraphs.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.