In a previous post I defined the network reliability problem. Briefly, we are given a directed graph whose edges are labelled with probabilities, which we can think of as giving the likelihood of a message successfully traversing a link in a network. The problem is then to compute the probability that a message will successfully traverse the network from a given source node to a given target node.

Several commenters pointed out the connection to Bayesian networks. I think they are right, and the network reliability problem is a very special case of Bayesian inference. However, so far this hasn’t seemed to help very much, since the things I can find about algorithms for Bayesian inference are either too general (e.g. allowing arbitrary functions at nodes) or too specific (e.g. only working for certain kinds of trees). So I’m going to put aside Bayesian inference for now; perhaps later I can come back to it.

In any case, Derek Elkins also made a comment which pointed to exactly what I wanted to talk about next.

Star semirings and path independence

Consider the related problem of computing the reliability of the single most reliable path from \(s\) to \(t\) in a network. This is really just a disguised version of the shortest path problem, so one can solve it using Dijkstra’s algorithm. But I want to discuss a more general way to think about solving it, using the theory of star semirings. Recall that a semiring is a set with two associative binary operations, “addition” and “multiplication”, which is a commutative monoid under addition, a monoid under multiplication, and where multiplication distributes over addition and \(0a = a0 = 0\). A star semiring is a semiring with an additional operation \((-)^*\) satisfying \(a^* = 1 + aa^* = 1 + a^*a\). Intuitively, \(a^* = 1 + a + a^2 + a^3 + \dots\) (though \(a^*\) can still be well-defined even when this infinite sum is not; we can at least say that if the infinite sum is defined, they must be equal). If \(S\) is a star semiring, then the semiring of \(n \times n\) matrices over \(S\) is also a star semiring; for details see Dolan (2013), O’Connor (2011), Penaloza (2005), and Lehmann (1977). In particular, there is a very nice functional algorithm for computing \(M^*\), with time complexity \(O(n^3)\) (Dolan 2013). (Of course, this is slower than Dijkstra’s algorithm, but unlike Dijkstra’s algorithm it also works for finding shortest paths in the presence of negative edge weights—in which case it is essentially the Floyd-Warshall algorithm.)

Now, given a graph \(G = (V,E)\) and labelling \(\varphi : E \to \mathbb{P}\), define the \(|V| \times |V|\) adjacency matrix \(M_G\) to be the matrix of edge probabilities, that is, \((M_G)_{uv} = \varphi(u,v)\). Let \((\mathbb{P}, \max, 0, \times, 1)\) be the star semiring of probabilities under maximum and multiplication (where \(a^* = 1\), since \(1 = \max(1,a \times 1)\)). Then we can solve the single most reliable path problem by computing \(M_G^*\) over this semiring, and finding the largest entry. If we want to find the actual most reliable path, and not just its reliability, we can instead work over the semiring \(\mathbb{P} \times E^*\), i.e. probabilities paired with paths. You might enjoy working out what the addition, multiplication, and star operations should be, or see O’Connor (2011).

In fact, as shown by O’Connor and Dolan, there are many algorithms that can be recast as computing the star of a matrix, for an appropriate choice of semiring: for example, (reflexive-)transitive closure; all-pairs shortest paths; Gaussian elimination; dataflow analysis; and solving certain knapsack problems. One might hope that there is similarly an appropriate semiring for the network reliability problem. But I have spent some time thinking about this and I do not know of one.

Consider again the simple example given at the start of the previous post:

For this example, we computed the reliability of the network to be \(0.835\), by computing the probability of the upper path, \(p = 0.45\), and the lower path, \(q = 0.7\), and then combining them as \(p + q - pq\), the probability of success on either path less the double-counted probability of simultaneous success on both.

Inspired by this example, one thing we might try would be to define operations \(p \land q = pq\) and \(p \lor q = p + q - pq\). But when we go to check the semiring laws, we run into a problem: distributivity does not hold! \(p \land (q \lor r) = p(q + r - qr) = pq + pr - pqr\), but \((p \land q) \lor (p \land r) = pq \lor pr = pq + pr - p^2qr\). The problem is that the addition operation \(p \lor q = p + q - pq\) implicitly assumes that the events with probabilities \(p\) and \(q\) are independent: otherwise the probability that they both happen is not actually equal to \(pq\). The events with probabilities \(pq\) and \(pr\), however, are not independent. In graph terms, they represent two paths with a shared subpath. In fact, our example computation at the beginning of the post was only correct since the two paths from \(s\) to \(t\) were completely independent.

Graph reduction

We can at least compute the reliability of series-parallel graphs whose terminals correspond with \(s\) and \(t\):

• If \(G\) consists of a single edge, return that edge’s probability.
• Otherwise, \(G\) is a composition of two subgraphs, whose reliabilities we recursively compute. Then:
  • If \(G\) is a sequential composition of graphs, return the product of their reliabilities.
  • If \(G\) is a parallel composition of two graphs with reliabilities \(p\) and \(q\), return \(p + q - pq\).

In the second case, having a parallel composition of graphs ensures that there are no shared edges between them, so \(p\) and \(q\) are indeed independent.

Of course, many interesting graphs are not series-parallel. The simplest graph for which the above does not work looks like this:

Suppose all the edges have probability \(1/3\). Can you find the reliability of this network?

More in a future post!

References