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'$?

  • $\begingroup$ This looks hopeless to have a nice formula isn't it ? $\endgroup$ – camomille Mar 20 '11 at 14:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Did Mar 20 '11 at 14:52
  • $\begingroup$ @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. $\endgroup$ – alyst Mar 20 '11 at 17:33

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.

| cite | improve this answer | |
  • $\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 Mar 20 '11 at 21:28

Your Answer

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

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