Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return Probabilities
Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return Probabilities
复制标题
DOI：
10.4230/lipics.icalp.2019.93
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Thomas Sauerwald;Luca Zanetti
中科院分区：
文献类型：
--
作者：
Thomas Sauerwald;Luca Zanetti
我们为各种随机步行数量建立并概括了几个边界，包括混合时间和最大打击时间。与以前的分析不同，我们的派生基于本地扩展属性的直观概念，这使我们能够捕获随机步行通过$ t $ step概率所取得的进展。我们将框架应用于动态变化的图表，其中固定了一组顶点，而边缘集则在每个回合中发生变化。对于在动态连接的图表上随机步行，固定分布不会随着时间而变化，我们表明它们的行为在某种意义上类似于静态图。例如，我们表明，$ d $的连接图的任何序列的混合和打击时间为$ o（n^2）$，概括了静态图的众所周知的结果。我们还根据图的等速度维度提供了精制的边界，与静态图再次匹配了已知的结果。最后，我们研究了并非总是连接的动态图上随机步行的属性：我们将它们的收敛与平均性与过渡矩阵平均值的光谱特性相关联，并提供了一些示例，这些示例证明了静态图和动态图之间有很强的差异。
We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allows us to capture the progress the random walk makes through $t$-step probabilities. We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round. For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of $d$-regular connected graphs is $O(n^2)$, generalising a well-known result for static graphs. We also provide refined bounds depending on the isoperimetric dimension of the graph, matching again known results for static graphs. Finally, we investigate properties of random walks on dynamic graphs that are not always connected: we relate their convergence to stationarity to the spectral properties of an average of transition matrices and provide some examples that demonstrate strong discrepancies between static and dynamic graphs.