研究如何进行随机，大规模，高效地数据运行

作者：Jakub Łącki,Slobodan Mitrović,Krzysztof Onak,Piotr Sankowski

摘要：我们引入了一种方法，可以在大图模型中有效地生成许多独立的随机游走，例如Massive Parallel Computation（MPC）模型。我们考虑每个机器的空间在顶点数量上强烈次线性的情况。在这种情况下，图形问题的许多自然方法都难以克服Θ（logn）MPC圆形复杂性障碍。我们设计了一种PageRank算法，即使对于有向图也可以打破这个障碍，并且还展示了如何打破这种双边性和扩展测试的障碍。

在无向的情况下，我们从静止分布开始随机游走，因此我们大致知道他们下一步的经验分布。这样我们就可以使用倍增方法提前准备采样行走的延续。我们的方法能够在MPC上以Θ（logl）轮生成多个长度为l的随机游走。此外，我们证明在\ textsc {2-Cycle}猜想下，这种圆形复杂性是渐近紧密的。随机漫游最重要的应用之一是PageRank计算。我们展示了如何使用我们的方法计算近似PageRank w.h.p.对于无向图上的O（loglogn）轮中的恒定阻尼因子（具有O~（m）总空间），以及有向图上的O~（loglogn）轮（具有O~（m + n1 + o（1））总空间）。

在我们的随机游走原语和传统属性测试算法的基础上，我们还展示了如何近似测试O（loglog（n））MPC轮次中的二分性和扩展。

原文标题：Walking Randomly, Massively, and Efficiently

原文摘要：

地址：https://arxiv.org/abs/1907.05391