未知のグラフに対する影響最大化アルゴリズムにおけるランダムジャンプの効果

摘要

我々はこれまで未知のグラフに対する影響最大化問題と、その発見的解法Influence Mamization for Unknown Graphs（IMUG）を提案している。未知のグラフに対する影響最大化問題は、限られた数のノードを探査することによって得られる部分的なソーシャルネットワークの構造のみから、そのネットワークにおける影響力の強いシードノードを特定することを目的とする。本稿では、これまでに提案した未知のグラフに対する影響最大化アルゴリズムIMUGにおけるグラフの探査方式を拡張し、その有効性を検証する。具体的には、IMUGの採用している貪欲的に次数の期待値の高いノードを探査する方式と、ランダムに選択したノードを探査するランダムジャンプを組み合わせた探査方式を用いたアルゴリズムIMUG with Random Flight（IMUG-RF）を提案し、その有効性を検証する。シミュレーション実験の結果、IMUG-RFが未知のグラフに対する影響最大化アルゴリズムとして効率的に動作することを示す。