講演情報
[B-16-15]マルコフ流束の近似保存を目的とした局所ノード縮約によるグラフ粗視化手法の一提案
◎△青山 和馬1、大崎 博之1 (1. 関西学院大学)
キーワード：
グラフ粗視化、ランダムウォーク
大規模情報ネットワークの解析効率化において、グラフ粗視化は重要な基盤技術である。しかし、従来手法の多くは静的なトポロジ構造の保存を主目的としており、ランダムウォークに代表される動的プロセスの保存を必ずしも保証しない。本研究では、無向グラフ上の単純ランダムウォークを対象に、定常流束の近似保存を目的とした局所ノード縮約型のグラフ粗視化手法 MAFCを提案する。提案手法では、粗視化に伴う近似的可集約性の損失を抑制するため、隣接スーパーノード間の条件付き遷移確率の類似性と内部流束の緊密性を組み合わせたコスト関数を定義し、貪欲にノード対を縮約する。確率的ブロックモデルを用いた評価実験の結果、提案手法はパラメータ設定に応じて、定常分布および第2固有値の保存誤差を既存の基準手法より低減できることを確認した。これにより、提案手法がランダムウォークの主要な動的特性を制御可能に保存する粗視化手法として有効であることを示す。