| Presentation | 2021-12-17 [Short Paper] A Study on First Passage Time and Cover Time of Non-backtracking Random Walk on a Graph Tetsuya Kawagishi, Jo Hagikura, Ryotaro Matsuo, Hiroyuki Ohsaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Recently, mathematical properties of random walks on a graph have been studied. Also, several extended models of a simple random walk, such as the non-backtracking random walk, the self-avoiding random walk, and the branching random walk, have been actively studied. The non-backtracking random walk is a simple random walk with a simple mechanism of prohibiting revisits to nodes that have been visited immediately before. The non-backtracking random walk is known to have better properties than a simple random walk. However, the effect of graph structure on the properties of the non-backtracking random has not been clarified well. In this paper, we derive the mean first passage time of the non-backtracking random walk on two types of graphs (i.e., random regular graphs and graphs generated by the configuration model) and the mean cover time of the non-backtracking random walk on random regular graphs. Furthermore, we analyze the impact of the graph structure on the mean first passage time and the mean cover time of the non-backtracking random walk by several numerical examples. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Random Walk / Mean First Passage Time / Mean Cover Time / Non-backtracking random walk / Random Regular Graph / Configuration Model |
| Paper # | IA2021-41 |
| Date of Issue | 2021-12-09 (IA) |
| Conference Information | |
| Committee | IN / IA |
|---|---|
| Conference Date | 2021/12/16(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Higashi-Senda campus, Hiroshima Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
| Chair | Kenji Ishida(Hiroshima City Univ.) / Tomoki Yoshihisa(Osaka Univ.) |
| Vice Chair | Kunio Hato(Internet Multifeed) / Toru Kondo(Hiroshima Univ.) / Yuichiro Hei(KDDI Research) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| Secretary | Kunio Hato(NTT) / Toru Kondo(Univ. of Nagasaki) / Yuichiro Hei(Nagaoka Univ. of Tech.) / Hiroshi Yamamoto(KDDI Research) |
| Assistant | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamurai(Fukuoka Univ.) / Daiki Nobayashi(Kyushu Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Information Networks / Technical Committee on Internet Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Short Paper] A Study on First Passage Time and Cover Time of Non-backtracking Random Walk on a Graph |
| Sub Title (in English) | |
| Keyword(1) | Random Walk |
| Keyword(2) | Mean First Passage Time |
| Keyword(3) | Mean Cover Time |
| Keyword(4) | Non-backtracking random walk |
| Keyword(5) | Random Regular Graph |
| Keyword(6) | Configuration Model |
| 1st Author's Name | Tetsuya Kawagishi |
| 1st Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 2nd Author's Name | Jo Hagikura |
| 2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 3rd Author's Name | Ryotaro Matsuo |
| 3rd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 4th Author's Name | Hiroyuki Ohsaki |
| 4th Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| Date | 2021-12-17 |
| Paper # | IA2021-41 |
| Volume (vol) | vol.121 |
| Number (no) | IA-300 |
| Page | pp.pp.56-59(IA), |
| #Pages | 4 |
| Date of Issue | 2021-12-09 (IA) |