0
$\begingroup$

I am working on a graph clustering algorithm (mcl). It gives the opportunity to give weights to the edges. The weights must be similarities, but I have a distance. The values of this distance range from 0 to infinity. I am looking for ways to convert this distance to a similarity. So far, my main idea is to use s = 1/(1+d).

Are there "better" alternatives? (and if so, how can I tell that a conversion is better than another?)

$\endgroup$
1
$\begingroup$

One way to increase or decrease contrast is to raise your s to a given power, e.g. s**0.5 to decrease contrast or s**2 to increase contrast. It is worthwhile noting that this can be done by mcl itself, using the -pi (pre-inflation) option, e.g. -pi 0.5 or -pi 2, so there is no need to create many different input files. In fact, mcl has a more general transformation option called -tf. The same effect can be achieved by supplying e.g. -tf 'pow(0.5)' or -tf 'pow(2)' (quotes are required to prevent the shell from interpreting these parentheses).

Now, to judge the merits of different conversions, you will need to wade in and have a look at the data and the clusterings you get and preferably use your knowledge of the domain to make informed choices. If you have gold-standard data (manual curation of some sort) it is possible to be a bit more systematic, for example in the case where the gold standard annotation can be viewed as a clustering.

Choose an edge-weight (similarity) cutoff such that the topology of the network becomes informative; i.e. too many edges or too few edges yield little discriminative information in the absence/presence structure of edges. Choose it such that no edges connect things you consider very dissimilar, and that edges connect things you consider somewhat similar to quite similar. In the case of mcl, the dynamic range in edge weight between 'a bit similar' and 'very similar' should be, as a rule of a thumb, one order of magnitude, i.e. two-fold or five-fold or ten-fold, as opposed to varying from 0.9 to 1.0.

$\endgroup$
1
$\begingroup$

Why is distance sometimes 0? In a graph, a distance of 0 would be a single node with itself. Are you sure you want to include those? Also, a distance of infinity would indicate no geodesic at all, are you sure you want to include those?

Assuming you answer "yes" to both questions: Is distance always an integer? If so, your solution seems fine. If not, then I would try various numbers instead of 1.

$\endgroup$
1
$\begingroup$

What is a similarity?

In many cases, you can just use $-distance$ as similarity. Because often, similarities may be negative in practise...

Secondly, what are you planning to do?

If you just sort by similarity, any monotone function will do.

If you want to retain certain mathematical properties, you will have to be more precise.

If e.g. your distance is naturally bounded to a maximum distance of 1, a reasonable way to convert back and forth is to take $1-d$. See for example Jaccard Similarity vs. Jaccard Distance. With potentially infinite distances, this will only work if you assume the maximum in your data is constant.

$\endgroup$

Your Answer

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

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