Cover time and mixing time of random walks on dynamic graphs
Cover time and mixing time of random walks on dynamic graphs
复制标题
动态图上随机游走的覆盖时间和混合时间
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Zvi Lotker
中科院分区：
文献类型：
--
作者：
C. Avin;M. Koucký;Zvi Lotker
图上简单随机游走的应用是一个强大的工具，在许多算法设置中非常有用，例如网络探索，采样，信息传播和分布式计算。这是由于简单随机游走仅依赖于本地数据，其可忽略的内存需求及其分布式特性。众所周知，对于静态图，覆盖时间，即访问图的每个节点的期望时间，和混合时间，即根据平稳分布对节点进行采样的时间，最多是相对于图的大小的多项式。受真实的世界网络（如对等网络和无线网络）的启发，本文的会议版本首次研究了任意动态网络上的随机游动。我们研究了最一般的模型，其中一个不经意的对手被允许改变图后的每一步的随机游走。与静态图相反，我们发现，即使在每个时间步网络都是良好连接和快速混合的，也存在对手策略，迫使动态图上简单随机游走的预期覆盖时间和混合时间呈指数级增长。为了解决这个问题，我们提出了一个简单的策略，懒惰的随机游走，它保证，在较小的条件下，多项式覆盖时间和多项式混合时间，无论对手所做的更改。
The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.
DOI：
10.1098/rspa.2009.0456
发表时间：
2010-03-08
影响因子：
3.5
作者：
Grindrod, Peter;Higham, Desmond J.
通讯作者：
Higham, Desmond J.