The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounded degree constant query testable properties shown to admit surprisingly space efficient algorithms. The main result of this paper is a space efficient single pass random order streaming algorithm for simulating nearly independent random walks that start at uniformly random vertices. We show that the distribution of $k$-step walks from $b$ vertices chosen uniformly at random can be approximated up to error $\varepsilon$ per walk using $(1/\varepsilon)^{O(k)} 2^{O(k^2)}\cdot b$ words of space with a single pass over a randomly ordered stream of edges, solving an open problem of Peng and Sohler [SODA `18]. Applications of our result include the estimation of the average return probability of the $k$-step walk (the trace of the $k^\text{th}$ power of the random walk matrix) as well as the estimation of PageRank. We complement our algorithm with a strong impossibility result for directed graphs.

翻译：随机顺序图流模式最近受到极大关注, 诸如匹配大小估计、 组件计数、 和对约束度常量查询测试属性的评估等问题显示, 可以接受令人惊讶的空间高效算法。 本文的主要结果是用于模拟以统一随机脊椎开始的几乎独立的随机行走的空间高效单个通过随机流算法。 我们的结果表明, 平均随机选取的 $b$ 的垂直行走, 其分配方式可以近似于误差 $\ varepsilon $/ ⁇ O( k)} 2 ⁇ O (k) ⁇ ⁇ cdot b$ 空间单词, 单过随机订购的边缘流, 解决 Peng 和 Sohler [SODA'18] 的开放问题。 我们结果的应用包括估计 $- rk$ 步行走的平均回程概率( ok ⁇ text{th} powergard) 以及 PageRank 的估算。 我们用直径图的绝对结果补充了我们的算法。