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
-
-
-
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.
- 5 more replies
New conversation -
-
-
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.
-
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.
- 4 more replies
New conversation -
-
-
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.
-
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.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.