Robustness of Random Walk on a Graph against Adversary Attacks

Random walk-based algorithms are frequently utilized to target node search and graph exploration in unknown graph structures. Unlike deterministic algorithms such as breadth-first search and depth-first search, target node search and graph exploration with random walk algorithms are expected to exhibit robustness against adversarial attacks because of their probabilistic nature. The characteristics of random walks when adversaries change the topology of the graph, known as adversarial attacks on random walks, have been just recently received attention. These attacks have been shown to significantly degrade the efficiency of target node search and graph exploration with random walks. However, questions regarding how robust random walks are against more realistic attacks persist. In this paper, we investigate adversarial attacks in the form of rewiring a limited number of links during target node search and graph exploration, particularly in scenarios where mobile agents employ random walk algorithms. The goal is to quantitatively determine how robust or vulnerable the conventional random walk algorithms are against link rewiring attacks. We consider three types of link rewiring attacks (centrality method, clustering method, and starting node method) and evaluate how they affect target node search (hitting time) and graph exploration time (cover time) of five major random walk algorithms on a graph - Simple Random Walk (SRW), Non-Backtracking Random Walk (NBRW), k-History random walk (k-History), Biased Random Walk (BiasedRW), and Vicinity Avoidance Random Walk (VARW) - in five graphs through simulation experiments.