most recent 30 from http://mathoverflow.net 2013-05-23T19:41:51Z http://mathoverflow.net/feeds/question/13987 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13987/distance-measure-on-weighted-directed-graphs Mitch Harris 2010-02-03T15:53:51Z 2010-02-03T18:10:36Z

<p>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.</p> <p>Can one devise a meaningful distance metric for weighted <i>directed</i> graphs? (assume non-negative weights and that the distance must be symmetric and have the triangular property)</p>

http://mathoverflow.net/questions/13987/distance-measure-on-weighted-directed-graphs/14014#14014 Greg Kuperberg 2010-02-03T18:10:36Z 2010-02-03T18:10:36Z

<p>Since you're asking for what is "meaningful", I think that one can then argue against some of the question.</p> <p>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.</p> <p>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.</p>