## The network reliability problem and star semirings

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

Dolan, Stephen. 2013. “Fun with Semirings: A Functional Pearl on the Abuse of Linear Algebra.” In ACM SIGPLAN Notices, 48:101–10. 9. ACM.

Lehmann, Daniel J. 1977. “Algebraic Structures for Transitive Closure.” Theoretical Computer Science 4 (1). Elsevier: 59–76.

O’Connor, Russell. 2011. “A Very General Method for Computing Shortest Paths.” http://r6.ca/blog/20110808T035622Z.html.

Penaloza, Rafael. 2005. “Algebraic Structures for Transitive Closure.” http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.7650.

Posted in math | | 9 Comments

## CCSC-Midsouth conference and programming contest

I’m in Memphis (again!) this weekend attending the 2016 CCSC Midsouth Regional Conference, which also has a student programming contest attached. I’m very proud of the two teams from Hendrix, who placed first and fifth out of 17 teams. This is now the third year in a row that a team from Hendrix has won the contest (though I had nothing to do with the first two!). The members of the winning team are all graduating this year, but each of the members of the other team will be around at least one more year, and I have talked to quite a few other students who are interested. I’m excited to continue building up a programming team with a tradition of excellence.

## CIS 194 materials now on github

I’ve been meaning for a while to put the source files for my CIS 194 materials in a publically accessible place, and I’ve finally gotten around to it: you can now find everything in byorgey/haskell-course on github.

I make no particular guarantees about anything; e.g. there is a crufty, complicated shake script that builds everything, but it probably doesn’t even compile with the latest version of Shake.

There are some obvious next steps, for which I have not the time:

1. Get everything building again
2. Fix any outstanding typos, confusions, etc.
3. Update it to be more specifically for general-audience learning rather than for a course at Penn
4. Find a permanent web home for the material. It’s sort of a happy accident that it has been accessible on the Penn site for so long, but it’s not a stable situation; I don’t even know who would have access to that site anymore.

All the material is licensed under a Creative Commons Attribution 4.0 International License, so go wild using it however you like, or working on the above next steps. Pull requests are very welcome, and I will likely give out commit access like candy.

Posted in haskell | Tagged , , , , , , , | 1 Comment

## Boltzmann sampling for generic Arbitrary instances

tl;dr: I know how to generate random instances of data types in a generic way, and even have some old code that already does all the hard work, but won’t have time to polish and package it until this summer. If you’re interested in helping, let me know!

This morning Kenny Foner pointed out to me this tweet by Gabriel Gonzales, asking why there isn’t a default Arbitrary instance for types implementing Generic. It reminded me that I’ve been meaning for a while now (years, in fact!) to get around to packaging up some code that does this.

As several pointed out on Twitter, this seems obvious, but it isn’t. It’s easy to write a generic Arbitrary instance, but hard to write one that generates a good distribution of values. The basic idea is clear: randomly pick a constructor, and then recursively generate random subtrees. The problem is that this is very likely to either blow up and generate gigantic (even infinite) trees, or to generate almost all tiny trees, or both. I wrote a post about this three years ago which illustrates the problem. It also explains half of the solution: generate random trees with a target size in mind, and throw out any which are not within some epsilon of the target size (crucially, stopping the generation early as soon as the tree being generated gets too big).

However, I never got around to explaining the other half of the solution: it’s crucially important to use the right probabilities when picking a constructor. With the wrong probabilities, you will spend too much time generating trees that are either too small or too big. The surprising thing is that with exactly the right probabilities, you can expect to wait only $O(n)$ time before generating a tree of size (approximately1) $n$.2

So, how does one pick the right probabilities? Essentially, you turn the generic description of your data type into a mutually recursive system of generating functions, and (numerically) find their radii of convergence, when thought of as functions in the complex plane. Using these values it is straightforward to compute the right probabilities to use. For the intrepid, this is explained in Duchon et. al3.

I have some old Haskell code from Alexis Darrasse which already does a bunch of the work. It would have to be updated a bit to work with modern libraries and with GHC.Generics, and packaged up to go on Hackage. I won’t really have time to work on this until the summer—but if anyone else is interested in working on this, let me know! I’d be happy to send you the code and provide some guidance in figuring it out.

1. The constant factor depends on how approximate you are willing to be.

2. I wanted to put an exclamation point at the end of that sentence, because this is really surprising. But it looked like $n$ factorial. So, here is the exclamation point: !

3. Duchon, Philippe, et al. “Boltzmann samplers for the random generation of combinatorial structures.” Combinatorics Probability and Computing 13.4-5 (2004): 577-625.

Posted in combinatorics, haskell, math, species | | 14 Comments

## At SIGCSE 2016 in Memphis

This weekend I’m in Memphis for SIGCSE 2016. This is my first time at SIGCSE, so I’m looking forward to picking up some new ideas in CS education, and more importantly to meeting lots of new people. If you’re here too, feel free to say hi!

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

Posted in math | Tagged , , , | 17 Comments

## A strange representation of Z6

On my other blog I am writing about a proof of the Lucas-Lehmer test, and today in the course of working up some examples I stumbled across this little gem.

Let $M$ be a monoid, and let $M^*$ denote the subset of elements of $M$ which actually have an inverse. Then it is not hard to show that $M^*$ is a group: the identity is its own inverse and hence is in $M^*$; it is closed under the monoid operation since if $a$ and $b$ have inverses then so does $ab$ (namely, $b^{-1}a^{-1}$); and clearly the inverse of every element in $M^*$ is also in $M^*$, because being an inverse also implies having one.

Now let $M = \{a + b\sqrt{3} \mid 0 \leq a,b < 3\}$, where the operation is multiplication, but the coefficients $a$ and $b$ are reduced modulo 3. For example, $(2 + \sqrt 3)(2 + 2 \sqrt 3) = (4 + 6) + (4 + 2) \sqrt 3 = 1 + 0 \sqrt 3$. This does turn out to be associative, and is clearly commutative; and $1 = 1 + 0\sqrt 3$ is the identity. I wrote a little program to see which elements have inverses, and it turns out that the three elements with $a = 0$ do not, but the other six do. So this is an Abelian group of order 6; but there’s only one such group, namely, the cyclic group $\mathbb{Z}_6$. And, sure enough, $M^*$ turns out to be generated by $2 + \sqrt 3$ and $2 + 2 \sqrt 3$.

Posted in math | Tagged , , , | 11 Comments