Marginalise edge weights on graph

Question

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a path divided by the sum of the scores of all paths.

I would like to compute the marginal probability of each edge; i.e., the probability that the edge is present in a path drawn randomly from the above probability distribution on paths. Is there an efficient algorithm to do this?

I know that I could simply calculate the probability of each path through the graph and then for each edge sum the probabilities of the paths on which the edge occurs but this seems a very inefficient way of doing things. Is there some way to use dynamic programming to solve this issue?

Answer 1

Yes, this can be solved with dynamic programming. In fact, it can be done in linear time.

I'll assume there is a single source $s$ and a single sink $t$ (if not, add $s$ and edges with score 0 from $s$ to each original source; and similarly for $t$).

Then, let $f(v)$ denote the sum of the scores of all paths from $s$ to $v$, and $f'(v)$ denote the number of such paths. You can compute both of them using dynamic programming. For instance,

$$f(v) = \sum_u f(u) + s(u,v)$$

where the sum is over all vertices $u$ such that $(u,v)$ is an edge in the graph, and where $s(u,v)$ denotes the score on the edge $(u,v)$. If you topologically sort the graph, then you can fill in the $f(v)$ values using the above recurrence in linear time. Similarly,

$$f'(v) = \sum_u f'(v)$$

which gives a way to fill in the $f'(v)$ values in linear time as well.

Let $g(v)$ denote the sum of the scores of all paths from $v$ to $t$, and $g'(v)$ the number of such paths. You can fill in these values similarly.

Finally, you can compute the marginal probability of an edge $(u,v)$ as

$$\Pr[(u,v)] = {f(u) g(v) + s(u,v) f'(u) g'(v) \over f(t)}.$$

The numerator has the total score of all paths that go through $(u,v)$, and the denominator has the total score of all paths in the graph.