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

14:00 〜 14:15学術奨励賞候補対象キャリアエクスプローラー

[B-16-16] 低次数ノード集約がランダムウォーク到着時間に与える影響に関する一検討

◎△伝田 和馬¹、ハン ネー アウン¹、大崎 博之¹ (1. 関西学院大学)

キーワード：

低次数ノード集約、ランダムウォーク、到着時間

ネットワーク上のランダムウォークにおける到着時間は、始点から目標ノードへ到達するまでの期待ステップ数を表し、探索、監視、分散的な情報取得の効率を評価する基本的な量である。ランダムウォークの遷移構造は、ノード間の接続関係を直接反映するため、局所的な構造変更であっても到着時間を変化させ得る。実際、高次関係を含むネットワークでは、ランダムウォークの定義や構造表現が遷移過程の性質に影響することが指摘されている。
大規模なグラフを扱う際には、次数1の葉ノードや次数2の中継的なノードを隣接ノードへ集約することが、解析対象を小さくする一つの方法になり得る。しかし、集約によって状態空間と接続関係が同時に変化するため、元のグラフで測られる到着時間と、集約後のグラフで測られる到着時間が同程度であるとは
限らない。そこで本稿では、無向重みなし連結グラフを対象として、葉ノードおよび次数2ノードの集約が、ランダムな始点から低次数目標ノードへの到達時間に与える影響を定量的に評価する。