社会ネットワーク上の情報伝搬における強影響力ノード抽出の効率化

摘要

広く用いられている二つの確率的情報伝搬の基本モデルに関して，大規模社会ネットワーク上で最も影響力が強いノード群を見つけるという，組合せ最適化問題を考察する．本最適化問題に関しては，貪欲戦略が高性能な近似解を提供できることが知られている．しかしながら，貪欲アルゴリズムに基づく従来手法では，与えられたノード集合から影響を受けるノード数の期待値の各周辺ゲインを推定する際，モデルのランダム過程を多数回シミュレーションするため，計算負荷が問題となっていた．本論文では，ボンドパーコレーションとグラフの強連結成分分解に基づいて，それらすべての周辺ゲインを効率的に推定する手法を提案し，貪欲アルゴリズムのもとで本最適化問題を近似的に解くことに適用する．そして，大規模な実世界ネットワークを用いた実験により，提案法は従来法よりも効率的であることを実証する.