Here’s another bite-sized stream algorithm for your delectation. This time we want to simulate a random walk from a given node in a graph whose edges arrive as an arbitrarily-ordered stream. I’ll allow you multiple passes and semi-streaming space, i.e., space where is the number of nodes in the graph. You need to return the final vertex of a length random walk.
This is trivial if you take passes: in each pass pick a random neighbor of the node picked in the last pass. Can you do it in fewer passes?
Well, here’s an algorithm from [Das Sarma, Gollapudi, Panigrahy] that simulates a random walk of length in space while only taking passes. As in the trivial algorithm, we build up the random walk sequentially. But rather than making a single hop of progress in each pass, we’ll construct the random walk by stitching together shorter random walks.
- We first compute short random walks from each node. Using the trivial algorithm, do a length walk from each node and let be the end point.
- We can’t reuse short random walks (otherwise the steps in the random walk won’t be independent) so let be the set of nodes from which we’re already taken a short random walk. To start, let and where is the vertex that is reached by the random walk constructed so far and is the length of this random walk.
- While
- If then set
- Otherwise, sample edges (with replacement) incident on each node in . Find the maximal path from such that on the -th visit to node , we take the -th edge that was sampled for node . The path terminates either when a node in is visited more than times or we reach a node that isn’t in . Reset to be the final node of this path and increase by the length of the path. (If we complete the length random walk during this process we may terminate at this point and return the current node.)
- Perform the remaining steps of the walk using the trivial algorithm.
So why does it work? First note that the maximum size of is because is only incremented when increases by at least and we know that . The total space required to store the vertices is . When we sample edges incident on each node in , this requires space. Hence the total space is . For the number of passes, note that when we need to take a pass to sample edges incident on , we make hops of progress because either we reach a node with an unused short walk or the walk uses samples edges. Hence, including the passes used at the start and end of the algorithm, the total number of passes is .
Das Sarma et al. also present a trade-off result that reduces the space to for any at the expense of increasing the number of passes to . They then use this for estimating the PageRank vector of the graph.
1 comment
Comments feed for this article
August 9, 2010 at 6:08 am
Open Problem: Random Walks « the polylogblog
[…] an earlier post, I sketched a result by [Das Sarma, Gollapudi, Panigrahy] that showed that it was possible to […]