2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Fantastic, I'll try that out! $\endgroup$ – 11thHeaven Jul 20 '18 at 18:31

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.