社会ネットワークの成長を考慮したィンフルエンスノード抽出手法

摘要

In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential nodes in a given social network, to perform a task of information diffusion. Kempe's method based on a general greedy algorithm can give a good approximate solution for the target set selection problem. However, the approximation performance of Kempe's method deteriorates because the method doesn't consider the change of the number of nodes and the number of edges of given network. In this paper, we propose a new method to extract the influential nodes efficiently from the dynamic social network.%本論文では，社会ネットワーク上の影響力が高いノード群(ターゲット集合)を発見するターゲット集合選択問題について述べる.ターゲット集合選択問題はNP困難であることが証明されており，この高性能な近似解法として，貪欲アルゴリズムに基づくKempeらの手法が知られている.し かし，Kempeらの手法は，社会ネットワークの動的変化を考慮していないため，ノード数ゃリンク数が変化するネットワークにおいて問題が生じる.本論文では，Kempeらの手法を時間経過と伴にネットワークを変化させながら情報拡散を行うように拡張し，拡散ノード数の期待値から高い影響力をもつノード群を発見するアルゴリズムを提案する.