Twitter | Pretraživanje | |
Object Of Objects
What's the fastest way to sample a random walk on a directed graph conditional on the start and end points?
Reply Retweet Označi sa "sviđa mi se" More
egbert b. gebstadter 24. sij
Odgovor korisniku/ci @ObjectOfObjects
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
Reply Retweet Označi sa "sviđa mi se"
Object Of Objects 24. sij
Odgovor korisniku/ci @npmedium
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.
Reply Retweet Označi sa "sviđa mi se"
GeniesLoki 24. sij
Odgovor korisniku/ci @ObjectOfObjects
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.
Reply Retweet Označi sa "sviđa mi se"
GeniesLoki 24. sij
Odgovor korisniku/ci @ObjectOfObjects
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.
Reply Retweet Označi sa "sviđa mi se"
Amateur Slacker 24. sij
Odgovor korisniku/ci @ObjectOfObjects
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.
Reply Retweet Označi sa "sviđa mi se"
Amateur Slacker 24. sij
Odgovor korisniku/ci @ObjectOfObjects
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.
Reply Retweet Označi sa "sviđa mi se"