Probability of preserving connectivity between pair of vertices in weighted graph

Question

Let $G=(V,E)$ be an undirected graph and $p \colon E \mapsto (0,1]$ defines weights of its edges.

Let's fix two connected vertices $v_1, v_2 \in V$.

Random graph $G'=(V,E')$ is obtained from $G$ by removing each edge $e \in E$ with probability $1-p(e)$.

What is the probability that connectivity between $v_1$ and $v_2$ is preserved in $G'$?

You definitely must tell more about the graph (and about the weight function) to get any answer at all. Compare the case of the line graph with $v_1$ and $v_2$ far apart to the case of the complete graph on $n$ vertices with $n$ large. — Did, Commented Mar 20, 2011 at 14:52
@Didier well, you right, that's implied part of the question -- if there are no nice results for arbitrary graph, maybe there are any non-trivial classes of graphs, where this problem is trackable? In my context it would be randomly generated scale-free network with number of edges that makes the brute force method unfeasible. — alyst, Commented Mar 20, 2011 at 17:33

Robert Israel · Accepted Answer · 2011-03-20 18:29:20Z

1

Let L be the set of all simple paths in G from $v_1$ to $v_2$. By inclusion-exclusion, the probability that $v_1$ and $v_2$ are connected is

$\sum_{A \subseteq L} (-1)^{|A|-1} P(\cup A \subseteq E')$

where for any set S of edges, $P(S \subseteq E') = \prod_{e \in S} p(e)$.

Although explicit computation won't be feasible for large graphs, under appropriate conditions this might be used to get asymptotics.

answered Mar 20, 2011 at 18:29

Robert Israel

54.2k1 gold badge76 silver badges152 bronze badges

$\begingroup$ Thanks, Robert. That gives an idea for an alternative formula: if $M$ is a collection of all minimal sets of edges, which removal disrupts connectivity between $v_1$ and $v_2$, then $1 - \sum_{B \subseteq M} (-1)^{|B|-1} P(\cup B \not\subseteq E')$ should also be the sought probability, where $P(S \not\subseteq E') = \prod_{e \in S} (1-p(e))$. $\endgroup$
– alyst
Commented Mar 20, 2011 at 21:28

Add a comment |

1 Answer 1