[B-16] インターネットアーキテクチャ

[B-16-11] A Study on Exploration Efficiency of $k$-Step Random Walks with Different Node Recording Schemes

^○吉次亮¹, 松尾涼太郎², 大崎博之¹, 中村遼² (1.関西学院大, 2.福岡大)

Keywords:ランダムウォーク

未知のグラフにおける対象ノードを発見するための手法として、ランダムウォークに基づくアルゴリズムが広く用いられている。ランダムウォークによる探査効率を向上する手法として、記憶領域を有するエージェントが過去に訪問したノードへの再訪を回避する手法が有効である。エージェントが有する記憶領域の大きさやその利用法によってランダムウォークの探査効率は大きく変化する。しかし、記憶領域を有するランダムウォークは解析的な取り扱いが容易でないことから、その特性はこれまで十分に明らかにされていない。大きさ k の記憶領域を有する k 履歴ランダムウォークにおいて、記憶領域に対する訪問ノードの記録方式の違いによってランダムウォークの探査効率がどの程度変化するかを実験により明らかにする。