Short random walks on graphs

被引：20
作者：
Barnes, G
Feige, U
机构：
[1] MAX PLANCK INST INFORMAT, SAARBRUCKEN, GERMANY
[2] WEIZMANN INST SCI, DEPT MATH APPL, IL-76100 REHOVOT, ISRAEL
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 1996年 / 9卷 / 01期
关键词：
random walk; graph; Markov chain;
D O I：
10.1137/S0895480194264988
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The short-term behavior of random walks on graphs is studied, in particular, the rate at which a random walk discovers new vertices and edges. A conjecture by Linial, that the expected time to find N distinct vertices is O(N-3) is proved. In addition, upper bounds of O(M(2)) on the expected time to traverse M edges and of O(MN) on the expected time to either visit N vertices or traverse M edges (whichever comes first) are proved.
引用
收藏
页码：19 / 28
页数：10
相关论文
共 50 条
  • [21] A NOTE ON RECURRENT RANDOM-WALKS ON GRAPHS
    TELCS, A
    [J]. JOURNAL OF STATISTICAL PHYSICS, 1990, 60 (5-6) : 801 - 807
  • [22] Relational Classification Using Random Walks in Graphs
    Kajdanowicz, Tomasz
    [J]. NEW GENERATION COMPUTING, 2015, 33 (04) : 409 - 424
  • [23] The Hitting Times of Random Walks on Bicyclic Graphs
    Zhu, Xiaomin
    Zhang, Xiao-Dong
    [J]. GRAPHS AND COMBINATORICS, 2021, 37 (06) : 2365 - 2386
  • [24] Random Walks on Graphs with Regular Volume Growth
    T. Coulhon
    A. Grigoryan
    [J]. Geometric & Functional Analysis GAFA, 1998, 8 : 656 - 701
  • [25] The Hitting Times of Random Walks on Bicyclic Graphs
    Xiaomin Zhu
    Xiao-Dong Zhang
    [J]. Graphs and Combinatorics, 2021, 37 : 2365 - 2386
  • [26] Relational Classification Using Random Walks in Graphs
    Tomasz Kajdanowicz
    [J]. New Generation Computing, 2015, 33 : 409 - 424
  • [27] Random Walks on Huge Graphs at Cache Efficiency
    Yang, Ke
    Ma, Xiaosong
    Thirumuruganathan, Saravanan
    Chen, Kang
    Wu, Yongwei
    [J]. PROCEEDINGS OF THE 28TH ACM SYMPOSIUM ON OPERATING SYSTEMS PRINCIPLES, SOSP 2021, 2021, : 311 - 326
  • [28] Random walks on graphs with volume and time doubling
    Telcs, Andras
    [J]. REVISTA MATEMATICA IBEROAMERICANA, 2006, 22 (01) : 17 - 54
  • [29] Generating Functions of Waiting Times and Numbers of Visits for Random Walks on Graphs
    Inoue, Kiyoshi
    Aki, Sigeo
    Narayanaswamy, Balakrishnan
    [J]. METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY, 2013, 15 (02) : 349 - 362
  • [30] Generating Functions of Waiting Times and Numbers of Visits for Random Walks on Graphs
    Kiyoshi Inoue
    Sigeo Aki
    Balakrishnan Narayanaswamy
    [J]. Methodology and Computing in Applied Probability, 2013, 15 : 349 - 362
12345