Exploration Efficiency of Random Walks in Dynamic Graph

Random walks on graphs have wide-ranging applications, including target node search on graphs and structural exploration of graphs. In recent years, analyses have been conducted not only on random walks over static graphs (where the topology does not evolve during the random walk) but also on dynamic graphs (where the topology evolves during the random walk). It has been shown that the behavior of a random walk on a random evolving graph is similar to that of a random walk on a static graph in that the stationary distribution remains unchanged over time. However, the impact of the dynamics (rate of change) of a dynamic graph on the characteristics of random walks, particularly the hitting time, has not been fully investigated. In this paper, we aim to quantitatively elucidate the search and exploration efficiency of random walks on various dynamic graphs. Specifically, we analyze the properties of random walks on a random evolving graph, and examine the impact of graph dynamics on search and exploration efficiency. As a consequence, we show that as the rate of change of the graph increases, the hitting time of the random walk operating on it decreases rapidly.