Random walks on randomly evolving graphs
Random walks on randomly evolving graphs
复制标题
随机演化图上的随机游走
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Luca Zanetti
中科院分区：
文献类型：
--
作者：
Leran Cai;Thomas Sauerwald;Luca Zanetti
随机游走是图上的一个基本随机过程，也是分布式算法设计中的一个关键原语。随机游走最重要的特征之一是，在温和的条件下，它们在时间上收敛到一个平稳的分布，该分布在图的大小中至多为多项式。然而，只有当图形不随时间变化时，这一基本属性才成立；另一方面，许多分布式网络本质上是动态的，它们的拓扑结构可能会发生巨大的变化。
A random walk is a basic stochastic process on graphs and a key primitive in the design of distributed algorithms. One of the most important features of random walks is that, under mild conditions, they converge to a stationary distribution in time that is at most polynomial in the size of the graph. This fundamental property, however, only holds if the graph does not change over time; on the other hand, many distributed networks are inherently dynamic, and their topology is subjected to potentially drastic changes.
DOI：
10.4230/lipics.icalp.2019.93
发表时间：
2019-03
期刊：
ArXiv
影响因子：
--
作者：
Thomas Sauerwald;Luca Zanetti
通讯作者：
Thomas Sauerwald;Luca Zanetti