<p>Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.   </p>

<p>Let $G=(V,E)$ be a simple connected graph. Each edge is of length 1. In addition, we assign directions to edges. Note that the graph is undirected, as we can traverse each edge in either direction. The assigned direction only determines the weight of each edge (either +1 or -1) depending on the direction of the traverse. </p>

<p>For each pair $v,u \in V$ of vertices, we define <i>anti-distance</i> $d(u,v)=-d(v,u)$, as the weighted average length of all the paths from $u$ to $v$. Note that the weights are dependent on the path and can be negative. The goal is to find $d(u,v)$ for all the pairs.</p>

<p>The algorithm I currently use is to generate many random spanning trees of $G$ (say, using the Aldous-Broder Algorithm), find $d(u,v)$ for each spanning tree (which is unambiguous and easy to find), and then average them all. </p>

<p>For our signal processing application, the input graphs have few hundreds nodes and it takes $\approx 10^5$ spanning trees to get  reasonable values. It is practical, but not pretty! The question is whether there is a better way to do this that does not need what is essentially amount to a Monte-Carlo simulation.</p>

CC BY-SA 3.0
2012-09-16T16:35:51.043Z
When you say "all the paths", you mean only simple paths, right? Do you have a reason to believe that your spanning tree algorithm converges to the correct average?
David Eppstein
CC BY-SA 3.0
2012-09-16T20:04:22.427Z
Yes, we are only interested in the simple paths from $u$ to $v$. I don't have a proof that the average of random  spanning trees method is correct. But intuitively the final results are consistent with what I expected them to be.
siravan
CC BY-SA 3.0
2012-09-17T12:55:31.093Z
How do you know that your approximate values are reasonable?...because they seem to converge?
Tyson Williams
CC BY-SA 3.0
2012-09-19T01:24:53.613Z
The main test is that when the algorithm is applied to small or regular graphs (e.g. rectangular grid), its result is consistent with one that is calculated analytically.
siravan
CC BY-SA 3.0
2014-06-19T20:56:33.410Z
What is the weight of a path?  What is the length of a path?  Is the length of a path the number of edges in it (regardless of edge directions)?  Is the weight of a path the product of the weights on the edges in the path, or the sum of the individual weights, or something?  You compute the weighted average of the lengths of all paths from $u$ to $v$; what are the weights in this weighted average?  Is each path weighted with its weight?
D.W.
CC BY-SA 3.0
2017-05-21T00:11:07.510Z
The algorithm you are using (via random spanning trees) does not work. Consider a simple $n$-cycle with edges directed clockwise. Let $(t,s)$ be any directed edge. Then there are two simple $s−t$ paths: $(s,t)$, or all remaining edges. So the anti-distance $d(s,t)$ is $−1⋅(1/2)+(n−1)⋅(1/2)=(n−2)/2$. But in a random spanning tree, the edge $(s,t)$ occurs with probability $1−1/n$, so the estimate returned by your algorithm for $d(s,t)$ (with enough samples) tends to $−1⋅(1−1/n)+(n−1)⋅(1/n)=0$.  [cc: @DavidEppstein]
Neal Young
<ds.algorithms><graph-theory><graph-algorithms><approximation><monte-carlo>
Finding all-pairs anti-distance
siravan
# Finding all-pairs anti-distance

(Asked by: username_0 on 2012-09-16)

Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.

Let $G=(V,E)$ be a simple connected graph. Each edge is of length 1. In addition, we assign directions to edges. Note that the graph is undirected, as we can traverse each edge in either direction. The assigned direction only determines the weight of each edge (either +1 or -1) depending on the direction of the traverse.

For each pair $v,u \in V$ of vertices, we define *anti-distance* $d(u,v)=-d(v,u)$, as the weighted average length of all the paths from $u$ to $v$. Note that the weights are dependent on the path and can be negative. The goal is to find $d(u,v)$ for all the pairs.

The algorithm I currently use is to generate many random spanning trees of $G$ (say, using the Aldous-Broder Algorithm), find $d(u,v)$ for each spanning tree (which is unambiguous and easy to find), and then average them all.

For our signal processing application, the input graphs have few hundreds nodes and it takes $\approx 10^5$ spanning trees to get reasonable values. It is practical, but not pretty! The question is whether there is a better way to do this that does not need what is essentially amount to a Monte-Carlo simulation.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, approximation, monte-carlo
> **Comments:**
> **username_1**: When you say "all the paths", you mean only simple paths, right? Do you have a reason to believe that your spanning tree algorithm converges to the correct average?  
> **username_0**: Yes, we are only interested in the simple paths from $u$ to $v$. I don't have a proof that the average of random  spanning trees method is correct. But intuitively the final results are consistent with what I expected them to be.  
> **username_2**: How do you know that your approximate values are reasonable?...because they seem to converge?  
> **username_0**: The main test is that when the algorithm is applied to small or regular graphs (e.g. rectangular grid), its result is consistent with one that is calculated analytically.  
> **username_3**: What is the weight of a path?  What is the length of a path?  Is the length of a path the number of edges in it (regardless of edge directions)?  Is the weight of a path the product of the weights on the edges in the path, or the sum of the individual weights, or something?  You compute the weighted average of the lengths of all paths from $u$ to $v$; what are the weights in this weighted average?  Is each path weighted with its weight?  
> **username_4**: The algorithm you are using (via random spanning trees) does not work. Consider a simple $n$-cycle with edges directed clockwise. Let $(t,s)$ be any directed edge. Then there are two simple $s−t$ paths: $(s,t)$, or all remaining edges. So the anti-distance $d(s,t)$ is $−1⋅(1/2)+(n−1)⋅(1/2)=(n−2)/2$. But in a random spanning tree, the edge $(s,t)$ occurs with probability $1−1/n$, so the estimate returned by your algorithm for $d(s,t)$ (with enough samples) tends to $−1⋅(1−1/n)+(n−1)⋅(1/n)=0$.  [cc: @DavidEppstein]  

---

## 0 answers

