電子情報通信学会総合大会講演要旨
B-11-24
未知のグラフに対する影響最大化アルゴリズムにおけるランダムジャンプの効果に関する一検討
○三原正大(関西学院大)・津川 翔(筑波大)・大崎博之(関西学院大)
近年、ソーシャルネットワーク上でのマーケティングや情報拡散を目的として、影響最大化問題の研究が活発に行われている。影響最大化問題は、与えられたソーシャルネットワークにおいて、ある影響伝搬モデルに従って少数のシードノードから影響を伝搬させた時に、影響を受けるノード数を最大化するシードノードの集合を特定することを目的とする。一般的な影響最大化問題では、ソーシャルネットワークの構造が全て与えられることを前提とするが、現実にはソーシャルネットワークの構造を完全に把握することは困難である。そこで我々は、限られた数のノードの探査によって得た部分的なソーシャルネットワークの構造のみを用いてシードノードを特定する未知のグラフに対する影響最大化問題の研究に取り組んでいる。未知のグラフに対する影響最大化問題においては、どのノードを探査するかが重要である。そこで本稿では、効果的な探査方法を明らかにすることを目的とし、従来の研究で用いているノード探査方法と、ランダムに選択したノードを探査する方法を組み合わせた探査方法が、未知のグラフに対する影響最大化においてどの程度有効であるかを評価する。