2
$\begingroup$

There is a simple and well-defined distance measure on weighted undirected graphs, namely the least sum of edge weights on any (simple) path between two vertices.

Can one devise a meaningful distance metric for weighted directed graphs? (assume non-negative weights and that the distance must be symmetric and have the triangular property)

$\endgroup$
6
  • $\begingroup$ Could you not do the same thing as with undirected graphs, which gives a non-symmetric metric D, and then symmetrize, i.e. define a metric d by d(x,y) = max{D(x,y), D(y,x)}? $\endgroup$ Feb 3, 2010 at 15:58
  • $\begingroup$ Yes...I had considered d(x,y) = (D(x,y)+D(y,x))/2 but that just didn't feel right. Did you mean 'min'? If so that seems much more satisfying for edge distance. but...I don't think it'll work for paths. $\endgroup$
    – Mitch
    Feb 3, 2010 at 16:07
  • 1
    $\begingroup$ Min does not satisfy the triangle inequality, only max does. $\endgroup$
    – domotorp
    Feb 3, 2010 at 16:23
  • 1
    $\begingroup$ Mitch, I meant max (and agree with domotorp). And yes, I also had it in mind that you could use + to symmetrize, rather than max. It sounds like you have some kind of design criteria in mind for how this distance should behave. Maybe you could add something to the question explaining them? (There's an "edit" button.) $\endgroup$ Feb 3, 2010 at 17:24
  • $\begingroup$ That min doesn't work but max does is not obvious to me (and I can't seem to think through it). Is there a short counterexample? $\endgroup$
    – Mitch
    Feb 3, 2010 at 20:24

1 Answer 1

6
$\begingroup$

Since you're asking for what is "meaningful", I think that one can then argue against some of the question.

The value of metrics on graphs in combinatorial geometry as an area of pure mathematics are more or less the same as their value in applied mathematics, for instance in direction-finding software in Garmin or Google Maps. In any such setting, the triangle inequality is essential for the metric interpretation, but the symmetry condition $d(x,y) = d(y,x)$ is not. An asymmetric metric captures the idea of one-way distance. You can have perfectly interesting geometry of many kinds without the symmetry condition. For instance, you can study asymmetric Banach norms such that $||\alpha x|| = \alpha ||x||$ for $\alpha > 0$, but $||x|| \ne ||-x||$, or the corresponding types of Finsler manifolds.

On the other hand, if you want to restore symmetry, you can. For instance, $$d'(x,y) = d(x,y) + d(y,x)$$ has a natural interpretation as round-trip distance, which again works equally well for pure and applied purposes. You can also use max, directly, or even min with a modified formula. Namely, you can define $d'$ to be the largest-distance metric such that $$d'(x,y) \le \min(d(x,y),d(y,x))$$ for all $x$ and $y$. All of these have natural interpretations. For instance, the min formula could make sense for streets that are one-way for cars but two-way for bicycles.

$\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.