14
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ 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? $\endgroup$
    – David Eppstein
    Sep 16, 2012 at 16:35
  • $\begingroup$ 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. $\endgroup$
    – siravan
    Sep 16, 2012 at 20:04
  • $\begingroup$ How do you know that your approximate values are reasonable?...because they seem to converge? $\endgroup$
    – Tyson Williams
    Sep 17, 2012 at 12:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – siravan
    Sep 19, 2012 at 1:24
  • 1
    $\begingroup$ 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] $\endgroup$
    – Neal Young
    May 21, 2017 at 0:11

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.