Cover Time in Edge-Uniform Stochastically-Evolving Graphs
Cover Time in Edge-Uniform Stochastically-Evolving Graphs
复制标题
边均匀随机演化图中的覆盖时间
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
I. Lamprou;R. Martin;P. Spirakis
定义了随机演化图的一个一般模型，即边一致随机演化图。在这个模型中，一个潜在的一般静态图的每一个可能的边缘独立地演化为活的或死的在每个离散的时间步的演化（马尔可夫）随机规则。随机规则对于每个可能的边缘是相同的，并且可以取决于边缘状态的过去k ≥ 0个观测。我们研究了在这样的动态图中发生的单个代理的两种随机游走：（i）具有延迟的随机游走（RWD），其中在每一步，代理选择（均匀随机）一个事件可能的边缘，即，一个事件的边缘在底层的静态图，然后，它等待，直到边缘变得活着遍历它。（ii）更自然的随机游走什么是可用的（RWA），其中代理只看活着的事件边缘在每个时间步和遍历其中一个均匀随机。我们的研究是关于覆盖时间的边界，即，每个节点至少被代理访问一次之前的预期时间。对于RWD，我们通过将RWD与静态图上的简单随机游走相关联，为k = 0，1的情况提供了第一个上界。此外，我们提出了一个修改的电网络理论捕捉k = 0的情况。对于RWA，我们推导出一些第一界的情况下，k = 0，通过减少RWA的RWD等价的步行修改延迟。此外，我们还提供了一个框架，显示计算的覆盖时间的精确值为一个一般家庭的随机演化图的指数时间。最后，我们在边均匀图中对RWA的覆盖时间进行了实验，并将实验结果与我们的理论界进行了比较。
We define a general model of stochastically-evolving graphs, namely the edge-uniform stochastically-evolving graphs. In this model, each possible edge of an underlying general static graph evolves independently being either alive or dead at each discrete time step of evolution following a (Markovian) stochastic rule. The stochastic rule is identical for each possible edge and may depend on the past k ≥ 0 observations of the edge’s state. We examine two kinds of random walks for a single agent taking place in such a dynamic graph: (i) The Random Walk with a Delay (RWD), where at each step, the agent chooses (uniformly at random) an incident possible edge, i.e., an incident edge in the underlying static graph, and then, it waits till the edge becomes alive to traverse it. (ii) The more natural Random Walk on what is Available (RWA), where the agent only looks at alive incident edges at each time step and traverses one of them uniformly at random. Our study is on bounding the cover time, i.e., the expected time until each node is visited at least once by the agent. For RWD, we provide a first upper bound for the cases k = 0 , 1 by correlating RWD with a simple random walk on a static graph. Moreover, we present a modified electrical network theory capturing the k = 0 case. For RWA, we derive some first bounds for the case k = 0 , by reducing RWA to an RWD-equivalent walk with a modified delay. Further, we also provide a framework that is shown to compute the exact value of the cover time for a general family of stochastically-evolving graphs in exponential time. Finally, we conduct experiments on the cover time of RWA in edge-uniform graphs and compare the experimental findings with our theoretical bounds.