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

[1H4-GS-1c-01] 忌避性・再訪性を考慮した自律的ネットワーク探索モデル

〇高島 浩司¹、﨑山 朋子² (1. 創価大学大学院、2. 創価大学理工学部)

キーワード：グラフ理論、ネットワーク探索

ネットワークは，場所を表すノードと接続を表すリンクによって構成される．現実世界のネットワークのほとんどは，スケールフリーネットワークである．スケールフリーネットワークは構造が複雑であるため，構造を理解するにはネットワーク探索が必要不可欠である．ネットワーク探索の代表的なモデルとしてランダムウォークモデルがある．ランダムウォークモデルは同じノードに複数回アクセスする可能性がある．改善モデルとして，訪問済みノードを一時的に訪問不可にする自己回避モデルがある．しかし，自己回避モデルは，ハブノードにすぐ戻ることができない場合がある．自己回避モデルよりも探索効率が良い，自己自律モデルを本論文で新たに提案する．自己自律モデルは，戻るべきハブノードに再訪問可能である．さらに、ネットワークのクラスター性も考慮する．本論文では提案モデルを使い，スケールフリーネットワーク上の移動時間を求め，従来モデルよりも探索効率が良いことを明らかにすることを目的とする．結果として、提案モデルである自己自律モデルは従来モデルである自己回避モデルより平均経路長が短く，探索効率が良いといえる．