Presentation Information
[B-16-14]A Study on a Link-Rewiring Attack for Delaying Random-Walk Search Based on Finite-Horizon Absorption Time
〇Taiyo Hirayama1, Han Nay Aung1, Hiroyuki Ohsaki1 (1. Department of Informatics, Graduate School of Science and Technology, Kwansei Gakuin University)
Keywords:
Random Walk,Adversarial Attack
Random walks are widely used for distributed search in networks with unknown structures, but they are vulnerable to link-rewiring attacks that significantly increase the first hitting time to a target node. The authors have previously shown that such attacks can delay random-walk search. However, existing methods rely on empirical indicators such as node degree and search-frontier boundaries, and are therefore not theoretically aligned with the objective of maximizing search delay. Realistic attackers are also subject to temporal constraints, since they can intervene only at fixed intervals. Nevertheless, conventional models assume an infinite-horizon objective and do not consider this interval. Such models tend to prefer topologies that trap the agent in the visited set for a long time, which can be inconsistent with short-term residence control before the next intervention. This study evaluates, through simulation, a finite-horizon formulation whose time scale is aligned with the intervention interval. Under the condition that the target node is unknown to both the searcher and the attacker, we experimentally clarify how the delay effect changes with the intervention interval.