## The network reliability problem

Let $G = (V,E)$ be a directed graph with vertices $V$ and edges $E$. Multiple edges between the same pair of vertices are allowed. For concreteness’ sake, think of the vertices as routers, and the edges as (one-way) connections. Let $\mathbb{P} = [0,1]$ denote the set of probabilities, and $\varphi : E \to \mathbb{P}$ be a function which assigns some probability to each edge. Think of $\varphi(e)$ as the probability that a single message sent along the edge $e$ from the source router will successfully reach the target router on the other end.

Suppose that when a router receives a message on an incoming connection, it immediately resends it on all outgoing connections. For $s,t \in V$, let $P(s,t)$ denote the probability that, under this “flooding” scenario, at least one copy of a message originating at $s$ will eventually reach $t$.

For example, consider the simple network shown below.

A message sent from $s$ along the upper route through $r$ has an $0.5 \times 0.9 = 0.45$ probability of arriving at $t$. By definition a message sent along the bottom route has an $0.7$ probability of arriving at $t$. One way to think about computing the overall probability $P(s,t)$ is to compute the probability that it is not the case that the message fails to traverse both links, that is, $1 - (1 - 0.45)(1 - 0.7) = 1 - 0.165 = 0.835$. Alternatively, in general we can see that $1 - (1 - p)(1 - q) = p + q - pq$, so $0.45 + 0.7 - 0.45 \times 0.7 = 0.835$ as well. Intuitively, since the two events are not mutually exclusive, if we add them we are double-counting the situation where both links work, so we subtract the probability of both working.

The question is, given some graph $G$ and some specified nodes $s$ and $t$, how can we efficiently compute $P(s,t)$? For now I am calling this the “network reliability problem” (though I fully expect someone to point out that it already has a name). Note that it might make the problem a bit easier to restrict to directed acyclic graphs; but the problem is still well-defined even in the presence of cycles.

This problem turned out to be surprisingly more difficult and interesting than it first appeared. In a future post or two I will explain my solution, with a Haskell implementation. In the meantime, feel free to chime in with thoughts, questions, solutions, or pointers to the literature.

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in math and tagged , , , . Bookmark the permalink.

### 17 Responses to The network reliability problem

1. sigfpe says:

At first I thought this was just straightforward matrix multiplication. But then I realized the algebraic structure we’re working in isn’t even a semi-ring so matrix multiplication doesn’t have the nice properties you expect. So I’m looking forward to your next installment!

• Brent says:

Right, exactly!

2. Derek Elkins says:

http://r6.ca/blog/20110808T035622Z.html

In the context of the above link.

data BY = R | S | T deriving (Eq, Ord, Enum, Bounded, Ix)

newtype Prob = Prob Double

instance Show Prob where show (Prob x) = show x
instance Semiring Prob where
zero = Prob 0
one = Prob 1
Prob x Prob y = Prob (x+y-x*y)
Prob x Prob y = Prob (x*y)

instance StarSemiring Prob where
star (Prob x) = Prob (recip (1 – x))

exampleProbMatrix :: Matrix BY Double
exampleProbMatrix = matrix value
where
value (R :-> R) = 0
value (R :-> S) = 0
value (R :-> T) = 0.9
value (S :-> R) = 0.5
value (S :-> S) = 0
value (S :-> T) = 0.7
value (T :-> R) = 0
value (T :-> S) = 0
value (T :-> T) = 0

o1 = printMatrix . fmap Prob $exampleProbMatrix o2 = printMatrix . star . fmap Prob$ exampleProbMatrix
~~~~

• Brent says:

That’s what I thought at first too. But that’s not actually a semiring.

• Brent says:

Wouldn’t you have to make a $2^n \times 2^n$ transition matrix, though? That is, the state space is actually the set of all subsets of graph vertices. Or did you have something more clever/efficient in mind?

3. Auke says:

In which sense is this different from belief propagation?

• Brent says:

Thanks for the pointer! I think I remember learning about belief propagation a long time ago in a Machine Learning class in grad school, but had forgotten about it. From looking into it briefly, it does seem related, but it doesn’t seem like exactly the same thing. If there is indeed a deeper connection I’d be happy to have it explained to me.

• Auke says:

It seems to me that the problem you are posing is to compute a marginal distribution from a bayesian network. This is exactly what the sum-product algorithm does.
David Barber’s “Bayesian Reasoning and Machine Learning” would be a reference on this. Personally I worked on some code implementing a belief propagation algorithm in Python, but there is a much bigger field surrounding this problem.

If you are not yet convinced, please let me know what needs explaining.

• Brent says:

OK, yes, I see now — I think you’re right. I had trouble seeing the connection before since Bayesian networks are so much more general (allowing arbitrary value types at nodes and allowing arbitrary functions expressing conditional probabilities).

4. blaisepascal2014 says:

Let’s make the problem a bit more complicated: Imagine an additional node ‘u’ with a single incoming edge from ‘t’ with a probability of 1.0. Is the network defined such that ‘u’ will receive the message twice 31.5% of the time?

An interesting question to explore is in a complex network what is the expected number of times that a node will see a message.

• Brent says:

If u has a single incoming edge from t with probability 1, then yes, it might see the message twice. The way I have defined the problem, that doesn’t matter, but I completely agree with you that it is also interesting to count the number of message copies a given node sees.

5. Wouter says:

Have you had a look at (Probabilistic) NetKAT?

• Brent says:

I am generally familiar with the work on NetKAT though not in great detail. Do you think it is connected somehow?