Random Walks on Evolving Graphs with Recurring Topologies
Random Walks on Evolving Graphs with Recurring Topologies
复制标题
具有循环拓扑的演化图上的随机游走
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
L. Rodrigues
中科院分区：
文献类型：
--
作者：
O. Denysyuk;L. Rodrigues
在本文中，我们考虑可以随时间变化的动态网络。通常，尽管不断发生不可预测的变化，但此类网络仍具有重复的模式。基于这一观察，我们引入了动态网络的 ρ 循环族的概念，它具有动态网络经常在族中包含图的特性，其中经常意味着比率 0<ρ ≤ 1。利用这个概念，我们将动态网络上最大度随机游走的分析简化为静态网络的情况。给定一个具有 ρ 循环族 \(\mathcal{F}\) 的动态网络，我们证明了 Open image in new window 关于命中和覆盖时间的上限，以及 \(O\left( \rho^{-1}(1- \hat\lambda(\mathcal{F}))^{-1} \log n \right) \) 的上限 随机游走的混合时间，其中 n 是节点数，\(\hat t_{hit}(\mathcal{F})\) 是 \(\mathcal{F}\) 中图命中时间的上限，\(\hat\lambda(\mathcal{F})\) 是第二大图的命中时间上限 \(\mathcal{F}\) 中图的转移矩阵的特征值。这些结果有两个含义。首先，它们在动态网络的命中时间和覆盖时间上产生 \(O\left( \rho^{-1} n^3 \log n \right) \) 的一般界限（ρ 是网络连接的速率）；这个结果改进了之前的边界 \(O\left( \rho^{-1} n^5 \log^2 n \right) \),[3]。其次，结果表明，具有循环族的动态网络保留了静态网络中随机游走的属性。此结果允许将静态图（派系、扩展器、常规图等）的广泛结果目录导入到动态设置中。
In this paper we consider dynamic networks that can change over time. Often, such networks have a repetitive pattern despite constant and otherwise unpredictable changes. Based on this observation, we introduce the notion of a ρ-recurring family of a dynamic network, which has the property that the dynamic network frequently contains a graph in the family, where frequently means at a rate 0<ρ ≤ 1. Using this concept, we reduce the analysis of max-degree random walks on dynamic networks to the case for static networks. Given a dynamic network with a ρ-recurring family \(\mathcal{F}\), we prove an upper bound of Open image in new window on the hitting and cover times, and an upper bound of \(O\left( \rho^{-1}(1- \hat\lambda(\mathcal{F}))^{-1} \log n \right) \) on the mixing time of random walks, where n is the number of nodes, \(\hat t_{hit}(\mathcal{F})\) is upper bound on the hitting time of graphs in \(\mathcal{F}\), and \(\hat\lambda(\mathcal{F})\) is upper bound on the second largest eigenvalue of the transition matrices of graphs in \(\mathcal{F}\). These results have two implications. First, they yield a general bound of \(O\left( \rho^{-1} n^3 \log n \right) \) on the hitting time and cover time of a dynamic network (ρ is the rate at which the network is connected); this result improves on the previous bound of \(O\left( \rho^{-1} n^5 \log^2 n \right) \),[3]. Second, the results imply that dynamic networks with recurring families preserve the properties of random walks in their static counterparts. This result allows importing the extensive catalogue of results for static graphs (cliques, expanders, regular graphs, etc.) into the dynamic setting.