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

[B-16-13] A Study on Proposing Random Walks on Graphs Using Bloom Filters

^○稲吉蓮¹, 吉次亮², Nay Aung Han², 大崎博之² (1.関西学院大, 2.関西学院大)

Keywords:ランダムウォーク、ブルームフィルタ、グラフ探索

グラフの探索にはランダムウォークを基にしたさまざまなアルゴリズムが広く用いられており、これらのアルゴリズムの効率化・高速化のためにはランダムウォークの探査効率の向上が重要である。例えば、未知のグラフにおいて、ある目的ノードを探索するという問題は、始点ノードから隣接ノードへの移動を繰り返すランダムウォークによって解くことができる。移動エージェントが過去に訪問したノードを記録することにより、ラン<ダムウォークの探査効率が大幅に改善できることが知られている。しかし、大規模なグラフでは多くのノードを記憶するために多量の記憶領域が必要となる。この課題を解決するためには、エージェントの効率的なメモリ使用法に関する検討が求められる。そこで本稿では、エージェントが有する少量の記憶領域を有効に活用することにより、大規模なグラフの効率的な探査を可能とするランダムウォーク手法の実現を目的とする。具体的には、スパムフィルタなどで利用されているブルームフィルタをランダムウォークに応用した BloomRW を提案するとともに、その有効性をシミュレーション実験によって調査する。