# Simulating Random Walks on Graphs in the Streaming Model

arXiv: https://arxiv.org/abs/1811.08205 · HTML: https://mlsanity.com/paper/1811.08205/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2018.

## Built on by (most cited first, 1 of 1)

- [Efficient and Local Parallel Random Walks](https://mlsanity.com/paper/2112.00655/) (2021)

## Abstract (arXiv)

We study the problem of approximately simulating a t-step random walk on a graph where the input edges come from a single-pass stream. The straightforward algorithm using reservoir sampling needs O(nt) words of memory. We show that this space complexity is near-optimal for directed graphs. For undirected graphs, we prove an Omega(n√t)-bit space lower bound, and give a near-optimal algorithm using O(n√t) words of space with 2^-Omega(√t) simulation error (defined as the ℓ1-distance between the output distribution of the simulation algorithm and the distribution of perfect random walks). We also discuss extending the algorithms to the turnstile model, where both insertion and deletion of edges can appear in the input stream.