Summary
International Conference on Emerging Technologies for Communications
2022
Session Number:S5
Session:
Number:S5-2
A Study on the Exploration Efficiency of (α, k) Random Walk on Unknown Graphs
Ryo Yoshitsugu, Takeaki Iwata, Ryotaro Matsuo, Hiroyuki Ohsaki,
pp.-
Publication Date:2022/11/29
Online ISSN:2188-5079
Summary:
Graph exploration with a random walk has a wide range of engineering applications, and its mathematical properties have been actively studied in recent years. Several mobility models have been proposed to improve the efficiency of a random walk, including weighted random walk, nonbacktracking random walk, and self-avoiding random walk. Some of these random-walk-based mobility models can be combined. However, what combinations of mobility models are suitable for graph exploration has not been sufficiently explored. In this study, we focus on an (a, k) random walk with the weight parameter a for transition probabilities and k avoidance slots used for self-avoidance to investigate the relationship between the setting of two parameters and the efficiency of graph exploration.