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

[B-16-12] A Study on Exploration Efficiency of Random Walks in Dynamic Graphs

^○中川大輝¹, 松尾涼太郎², 大崎博之¹ (1.関西学院大, 2.福岡大)

この講演は本会「学術奨励賞受賞候補者」の資格対象です。

Keywords:ランダムウォーク

グラフ上のランダムウォークは、グラフ上の対象ノード探索やグラフの構造探査など幅広い用途への応用が可能である。近年、静的な (トポロジがランダムウォーク中に変化しない) グラフ上のランダムウォークだけでなく、動的な (トポロジがランダムウォーク中に変化する) グラフ上のランダムウォークの特性分析も行なわれつつある。これまで、エージェントの遷移確率が定常であるような任意の動的グラフにおけ
る、最悪時の平均初回到着時間のオーダは、静的グラフにおける最悪時の平均初回到着時間のオーダと等しい(グラフのノード数をnとした時にO(n^3)となる) ことが解析的に明らかにされている。しかし、動的グラフ上のランダムウォークの平均的な特性はこれまで十分明らかにされていない。そこで、さまざまな静的グラフと動的グラフにおけるランダムウォークの平均初回到着時間と被覆時間を分析することにより、グラフのダイナミクスがランダムウォークの特性に与える影響を定量的に明らかにする。