0
$\begingroup$

Hi guys, let's say I have a connected, undirected graph with many nodes. I am interested in finding the probability that an edge appears in any spanning tree of the graph. I could apply some of the suggestions given in Number of spanning trees which contain a given edge but the problem is each spanning tree of the graph is not assigned an equal probability.

For the original graph structure, we assign a non-zero weight to every edge. For each spanning tree, we take the product $P_i$ of all the weights of the edges present in that tree. The probability of this spanning tree is then computed as $\frac{P_i}{Z}$ where $Z = \sum_i P_i$ is the normalization term. $Z$ has a closed form expression in terms of the determinant (cf. http://www.ri.cmu.edu/pub_files/pub2/meila_marina_2000_1/meila_marina_2000_1.pdf).

I have tried to enumerate all spanning trees of the graph and check if the edge appears in the spanning tree and sum all the probabilities of the relevant spanning trees. Unfortunately, MATLAB cannot deal with a large number of data along the process (10^32 spanning trees in my case). I was wondering if anyone has a more efficient way of finding the probability of an edge appearing in a spanning tree. Perhaps some closed-form solution?

Any insights?

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ The matrix-tree theorem still holds with weights. $\endgroup$
    – Qiaochu Yuan
    Jun 21, 2012 at 6:03
  • $\begingroup$ Hi qiaochu, thanks for the insight! The other question that has been boggling me now is the case when I am interested in computing the probability that a set of edges will appear in any spanning tree. Say I have $e_1$ and $e_2$ as the 2 edges and I'm interested in $P(e_1 \subset T \cap e_2 \subset T)$ where $T$ is the set of all spanning trees. Quoting the above paper, the edges $e_1$ and $e_2$ are not independent since $T_i$ has to be a spanning tree. Thus, $P(e_1 \subset T \cap e_2 \subset T) \neq P(e_1 \subset T)P(e_2 \subset T)$. In this case, following your comment in the other post, $\endgroup$
    – user24603
    Jun 21, 2012 at 7:29
  • $\begingroup$ ^continued... do you suggest letting 2 variables, one for $e_1$ and $e_2$, say $t_1$ and $t_2$ and setting them simultaneously to 0 and 1? Thanks for your valuable suggestions! $\endgroup$
    – user24603
    Jun 21, 2012 at 7:30
  • 1
    $\begingroup$ Let $S(t_1,t_2)$ be the weighted count of spanning trees giving $e_i$ the weight $t_i$. By inclusion-exclusion, the count of spanning trees containing both is $S(1,1)−S(1,0)−S(0,1)+S(0,0)$. You could also simply contract the edges to get a new graph with $2$ fewer vertices. $\endgroup$
    – Douglas Zare
    Jun 21, 2012 at 12:49

1 Answer 1

Reset to default
5
$\begingroup$

Qiaochu gave the gist of the solution, but here is an observation and a new question. Suppose $e$ is the edge from $i$ to $j$ ($i\lt j$) and has weight $w$. Let $A$ be the Laplace/Kirchoff matrix with row $j$ and column $j$ struck out. Then $|A|$ is the (weighted) number of spanning trees, as we know. Deleting the edge $e$ just subtracts $w$ from the $i$-th diagonal entry of $A$; call that matrix $A_e$ and note that $|A_e|$ is the number of spanning trees that avoid $e$. So $P_e = |A_e|/|A|$ is the probability that a random spanning tree avoids $e$. However, $A_e$ differs from $A$ only in the $i$-th column, so using Cramer's rule backwards we find that $P_e$ is the $i$-th entry of $\boldsymbol x$, where $A\boldsymbol{x}=\boldsymbol{b}$ and $\boldsymbol{b}$ is the $i$-th column of $A$ with $w$ subtracted from the $i$-th entry.

In other words, we can forget determinants and find $P_e$ by solving one linear equation.

The extra question is whether additional probabilities (e.g., the probability of avoiding a given set of edges) can also be found with a single linear equation solution. Inclusion-exclusion gets exponential pretty quick...

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.