|
@ObjectOfObjects | |||||
|
What's the fastest way to sample a random walk on a directed graph conditional on the start and end points?
|
||||||
|
||||||
|
egbert b. gebstadter
@npmedium
|
24. sij |
|
If acyclic, go depth first from source and remove all edges that don't eventually lead to sink
then walk randomly uniform over the edges
sounds optimal? O(V + E) or something
|
||
|
|
||
|
Object Of Objects
@ObjectOfObjects
|
24. sij |
|
I actually need it to work for acyclic graphs.
Also, this won't produce the correct distribution because it doesn't penalize entering nodes that had a lot of dead end out-edges.
|
||
|
|
||
|
GeniesLoki
@GeniesLoki
|
24. sij |
|
I haven't checked details but I think following works:
Precompute P(ever reaches desired end given uniform walk) using linear algebra
Beginning at start, walk sampling each node with weight proportional to the precomputed probability.
|
||
|
|
||
|
GeniesLoki
@GeniesLoki
|
24. sij |
|
This should work. Certainly it gives you a random walk of the right type, and it produces the right answer for sure if all nodes have the same number of out edges (it's a Boltzmann sampler then) but like I say haven't checked details.
|
||
|
|
||
|
Amateur Slacker
@noop_noob
|
24. sij |
|
Assumption: this is an acyclic graph, and you want each path to have equal probability of occurring.
Do a topological sort of the graph. Then, using this sorted order, use dynamic programming to label each node with the number of paths from that node to the destination node.
|
||
|
|
||
|
Amateur Slacker
@noop_noob
|
24. sij |
|
Finally, sample a path, choosing each node in the path randomly one-by-one. At each step, look at all the possible next nodes, and make the probability of choosing a certain next node proportional to the number on its label.
|
||
|
|
||