Extracting Influential Nodes for Information Diffusion on a Social Network
-
Masahiro Kimura, Kazumi Saito, Ryohei Nakano
-
AAAI 2007
概要
-
influence maximizationの高速アルゴリズム
提案手法
-
ICもLTもランダムグラフを考えればいい
-
σの増加量を効率的にもとめる
-
事前にランダムグラフを作っておく
-
シード集合: A
-
Aから到達可能な頂点を除く
-
頂点uについて,↑で出来たグラフでuから到達可能な頂点数Fをもとめる
-
uと同じ連結成分に入っている頂点vについて,σ_i(A∪{v})=σ_i(A)+Fとする
実験
-
250K辺のが最大
-
ICはp=0.1,LTは次数重み
-
提案手法の方がシミュレーション回数が少なくても良い解が出せている
-
現状のシード集合に関するσは全部同じだから依存しないため,みたいな説明
-
最大で数千倍高速化
まとめ
-
StaticGreedyにかなり近いので驚いた,強連結成分も考慮しているのでもう少し効率が良い
-
回数が少なくても良い解が出る説明もしているので良い
AAAI influence maximization
2014-02-15 01:20:37 (Sat)
最終更新:2014年02月15日 01:20