Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
6  
The matrix-tree theorem still holds with weights. –  Qiaochu Yuan Jun 21 '12 at 6:03
    
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, –  user24603 Jun 21 '12 at 7:29
    
^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! –  user24603 Jun 21 '12 at 7:30
1  
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. –  Douglas Zare Jun 21 '12 at 12:49
add comment

1 Answer

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...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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