[1H4-GS-1c] 基礎・理論：アルゴリズム

[1H4-GS-1c-01] Autonomous network exploration model considering the self-avoiding and the revisit

〇Koji Takashima¹, Tomoko Sakiyama² (1. Graduate School of Soka University, 2. Faculty of Science and Engineering, Soka University)

Keywords:Graph theory, Network exploration

Scale-free networks are constructed by nodes and by links that represent places and connections respectively. Autonomous network exploration is essential to understand the structure of scale-free networks. The random walk model and the self-avoiding walk model are well known as representative network exploration models. The problem of the simple random walk model is that the agent revisits nodes repeatedly. The problem of the self-avoiding walk model is that the agent fails to revisit hub nodes. To solve these two problems, we propose the self-autonomous walk model as a new network exploration model. The self-autonomous model can return to hub nodes and is unaffected by network clusters. In this paper, we use the proposed model to find the average path length on the scale-free network and aim to improve the exploration efficiency compared to conventional models. As a result, the proposed model achieves shorter path lengths than conventional models.