| Presentation | 2022-12-13 A Study on Effect of Laziness of Random Walk on Efficiency of Graph Exploration in Dynamic Graphs Daiki Nakagawa, Takeaki Iwata, Ryotaro Matsuo, Hiroyuki Ohsaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Graph exploration with a random walk has a wide range of engineering applications, and its mathematical properties have been actively studied. In recent years, not only random walks on static graphs (topology structure does not change over time), but also random walks on dynamic graphs (topology structure changes over time) have attracted a lot of attention. It has been shown that on an evolving graph (a type of dynamic graphs), the cover time of a random walk can be reduced to polynomial time by introducing laziness to a simple random walk. However, to the best of our knowledge, the effect of random walk laziness on the properties of the cover time of the random walk under a typical environment have not been sufficiently clarified. In this study, we therefore investigate the effect of random walk laziness on the random walk properties for a variety of evolving graphs with different sizes and densities. Specifically, we artificially generate Markov evolving graphs by generating various graphs with different structure, size, and density using seven different graph generation models and randomly rearranging the links in these graphs by rate τ, and we compare the mean cover time and mean first passage time of a lazy random walk on its Markovian dynamic graph with those of a simple random walk. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Random Walk / Lazy Random Walk / Evolving Graph / Mean First Passage Time / Mean Cover Time |
| Paper # | IA2022-57 |
| Date of Issue | 2022-12-05 (IA) |
| Conference Information | |
| Committee | IN / IA |
|---|---|
| Conference Date | 2022/12/12(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 | Kunio Hato(Internet Multifeed) / Tomoki Yoshihisa(Osaka Univ.) |
| Vice Chair | Tsutomu Murase(Nagoya Univ.) / Yusuke Sakumoto(Kwansei Gakuin Univ.) / Yuichiro Hei(KDDI Research) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| Secretary | Tsutomu Murase(KDDI Research) / Yusuke Sakumoto(Nagaoka Univ. of Tech.) / Yuichiro Hei(NTT) / Hiroshi Yamamoto(NTT) |
| Assistant | / Daisuke Kotani(Kyoto Univ.) / Ryo Nakamura(Fukuoka Univ.) / Ryo Nakamura(Univ. of Tokyo) |
| 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) | A Study on Effect of Laziness of Random Walk on Efficiency of Graph Exploration in Dynamic Graphs |
| Sub Title (in English) | |
| Keyword(1) | Random Walk |
| Keyword(2) | Lazy Random Walk |
| Keyword(3) | Evolving Graph |
| Keyword(4) | Mean First Passage Time |
| Keyword(5) | Mean Cover Time |
| 1st Author's Name | Daiki Nakagawa |
| 1st Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 2nd Author's Name | Takeaki Iwata |
| 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 | 2022-12-13 |
| Paper # | IA2022-57 |
| Volume (vol) | vol.122 |
| Number (no) | IA-306 |
| Page | pp.pp.50-55(IA), |
| #Pages | 6 |
| Date of Issue | 2022-12-05 (IA) |