On the Efficiency of Biased Random Walk with History on a Graph

Random walks are used for graph exploration in a wide range of engineering applications. In recent years, their mathematical properties have been actively studied. To optimize random walks, various mobility models have been developed, such as weighted random walk, non-backtracking random walk, self-avoiding random walk, and vicinity-avoiding random walk. Although some of these random walk models can be combined, it has not yet been adequately clarified how to combine those random walk models under different environments. The impact of memory management strategies of random walks with history on different types of graphs has also not been clarified. Therefore, this study focuses on (α, k) random walk, with the transition probability weight parameter α and the self-avoidance memory size parameter k, to clarify the relationship between two parameter settings and its efficiency of node search and graph exploration. Additionally, we investigate how the choice of memory management strategy (i.e., FIFO (First-In, First-Out) and LRU (Least Recently Used)) affects the efficiency of graph exploration. Simulation experiments are conducted to measure the node search time (average hitting time) and the graph exploration time (average cover time) when running different random walks with varying (α, k) parameter settings and memory management strategies on graphs generated with seven different network generation models.