How Slow, or Fast, Are Standard Random Walks? - Analyses of Hitting and Cover Times on Tree
How Slow, or Fast, Are Standard Random Walks? - Analyses of Hitting and Cover Times on Tree
复制标题
标准随机游走有多慢或多快？
DOI：
10.1007/978-3-642-02427-6_18
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Yamashita
中科院分区：
文献类型：
--
作者：
Yoshiaki Nonaka;H. Ono;S. Kijima;M. Yamashita
随机游走是一个强大的工具，不仅用于建模，而且用于实际应用，如互联网爬虫。图上的标准随机游动已经得到了很好的研究;众所周知，对于任何n阶图，标准随机游动的命中时间和覆盖时间都是O（n3）有界的，并且对于某些图，这个界是紧的。Ikeda et al.（2003）提出了“β-random walk”，它实现了任何图的O（n2）命中时间和O（n2 log n）覆盖时间，因此在某种意义上，它比标准的随机游走有“n倍的改进”。
本文通过比较标准随机游动和最快随机游动，讨论了击中次数和覆盖次数的优化问题。我们证明了对于任何树，标准随机游走的命中时间至多是最快随机游走的时间的O（n）倍。同样，对于任何树，标准随机游走的覆盖时间最多比最快的随机游走的覆盖时间长O（√n log n）-倍。我们还通过例子证明了我们的击中时间的界是紧的，而我们只给出了覆盖时间的下界Ω（n/log n）.
Random walk is a powerful tool, not only for modeling, but also for practical use such as the Internet crawlers. Standard random walks on graphs have been well studied; It is well-known that both hitting time and cover time of a standard random walk are bounded by O(n3) for any graph with n vertices, besides the bound is tight for some graphs. Ikeda et al. (2003) provided "β-random walk," which realizes O(n2) hitting time and O(n2 log n) cover times for any graph, thus it archives, in a sense, "n-times improvement" compared to the standard random walk.
This paper is concerned with optimizations of hitting and cover times, by drawing a comparison between the standard random walk and the fastest random walk. We show for any tree that the hitting time of the standard random walk is at most O(n)-times longer than one of the fastest random walk. Similarly, the cover time of the standard random walk is at most O(√n log n)-times longer than the fastest one, for any tree. We also show that our bound for the hitting time is tight by giving examples, while we only give a lower bound Ω(√n/log n) for the cover time.
有限图上具有局部信息的随机游走
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
Nobuhiro Asai;Izumi Kubo;Hui-Hsiung Kuo;Toshio Nakata;Nobuhiro Asai;Izumi Kubo;Toshio Nakata;Nobuhiro Asai;谷口 礼偉;Hirotake Yaguchi;Nobuhiro Asai;Nobuhiro Asai;Nobuhiro Asai;Hisashi Yokota;Hisashi Yokota;Nobuhiro Asai;Nobuhiro Asai;中田 寿夫;Toshio Nakata;谷口 礼偉;Hirotake Yaguchi;Tatsuhiro Honda;Tatsuhiro HONDA;Nobuhiro Asai;Nobuhiro Asai;谷口 礼偉;Hirotake Yaguchi;Nobuhiro Asai;Nobuhiro Asai;Nobuhiro Asai;Hirotake Yaguchi;Hirotake Yaguchi;Tatsuhiro Honda;Tatsuhiro Honda;池田 諭;Satoshi Ikeda
通讯作者：
Satoshi Ikeda