I have two sets of nodes A and B with size L and M on graph.

For every nodes in set A, I'm computing minimum length shortest path to nodes in set B(at the end for each node, I have just one minimum length shortest path).Then I sum it up (summing up for the nodes in set A) and normalize it by the size of set A

How can I show that this is distance metric and satisfy triangle inequality? Ofcourse I know that distance from A->B might not equal to B->A, but can I set it to equal by definition ? I mean, I want to set dist(A-B)=dist(B-A)

  • 2
    $\begingroup$ I don't think it is; for one thing, it's not symmetric. If your graph looks like a1 a2 b1 ............ b2 with $A = \{a_1, a_2\}$ and $B = \{b_1, b_2\}$, then the average distance from a node in $A$ to $B$ is $1.5$, but (because of $b_2$) the average distance from a node in $B$ to $A$ is huge. $\endgroup$ – Misha Lavrov Oct 24 '17 at 16:23
  • $\begingroup$ Well, suppose I take the final distance as average of distance in both direction. then , distance from A->B will be the same as B->A. Also is it wrong that, by defination, I set distance of A->B equal to B->A ? $\endgroup$ – user2806363 Oct 24 '17 at 17:16
  • $\begingroup$ It's not wrong to do that, but then you're using a definition that's different from the one in your question, which doesn't do this. $\endgroup$ – Misha Lavrov Oct 24 '17 at 17:22
  • $\begingroup$ Sounds good. Do you know how can I prove that triangle inequality holds for this case ? $\endgroup$ – user2806363 Oct 24 '17 at 17:31

As I pointed out in the comment, the original definition is not symmetric. There are several ways to fix this, but not all of them will satisfy the triangle inequality.

Let $D(A,B)$ be the function you've defined above: the minimum distance from $a$ to $B$, averaged over all $a \in A$. We could try replacing this with

  • $\min\{D(A,B), D(B,A)\}$ or
  • $\frac12(D(A,B) + D(B,A))$ or
  • $\max\{D(A,B), D(B,A)\}$

but none of these satisfy the triangle inequality. Consider a path on $6$ vertices $a_1, a_2, b_1, b_2, c_1, c_2$ in that order, and let $A =\{a_1, a_2\}$, $B = \{b_1, b_2\}$, $C = \{c_1, c_2\}$. Then $D(A,B) = D(B,A) = 1.5$, so any approach to "fixing the symmetry" would leave the distance between them at $1.5$. Similarly, $D(B,C) = D(C,B) = 1.5$. But $D(A,C) = D(C,A) = 3.5$, and $3.5 > 1.5 + 1.5$, so the triangle inequality is not satisfied.

What does work is defining the distance between vertex sets $A$ and $B$ to be the graph distance $d(a,b)$ averaged over all pairs $(a,b) \in A \times B$. Let $D^*(A,B)$ be this average.

This satisfies the triangle inequality: if $A, B, C$ are any vertex sets, then by the graph distance triangle inequality we have $d(a,b) + d(b,c) \ge d(a,c)$ for any $a\in A$, $b\in B$, and $c\in C$. Therefore $$\frac{1}{|A||B||C|}\sum_{a \in A}\sum_{b\in B}\sum_{c \in C}(d(a,b)+d(b,c)) \ge \frac{1}{|A||B||C|}\sum_{a \in A}\sum_{b\in B}\sum_{c \in C} d(a,c)$$ and this simplifies to $$D^*(A,B) + D^*(B,C) \ge D^*(A,C).$$

It does still have the problem that $D^*(A,A) \ne 0$, so it's still not quite a metric...

  • $\begingroup$ Good, but I think (1-cor(Dist)) would fix it. Don't think so ? $\endgroup$ – user2806363 Oct 24 '17 at 19:24
  • $\begingroup$ Could you elaborate? $\endgroup$ – Misha Lavrov Oct 24 '17 at 19:30

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.