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.

$\endgroup$
  • 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 '12 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 '12 at 20:04
  • $\begingroup$ How do you know that your approximate values are reasonable?...because they seem to converge? $\endgroup$ – Tyson Williams Sep 17 '12 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 '12 at 1:24
  • $\begingroup$ 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? $\endgroup$ – D.W. Jun 19 '14 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.