Efficient algorithms for influence maximization in social networks
-
Yi-Cheng Chen, Wen-Chih Peng, Suh-Yin Lee
-
KAIS 2012
概要
-
CDH: Community and Degree Heuristic
-
CDH-KcutとCDH-SHRINK
Heat diffusion model (HDM)
-
熱拡散(物理現象)
-
f_i(t): 時刻tでのv_iの熱
-
初期状態t=0が与えられる
-
近傍からΔtの間影響を受ける
-
iの変化量 = αΣ_j [f_j(t)-f_i(t)]
-
熱がθを超えたらアクティブになったとする
-
シードに対してf(t_0)=h_0とセットする
コミュニティ検出
-
KcutとSHRINKはO(m log n)で動く
Community and Degree Heuristic
-
グラフをコミュニティに分割
-
各々で大事な頂点を選ぶ
-
影響が被らないように(損するから)選ぶ
-
元のグラフに対応する頂点を選ぶ
-
コミュニティ外にはあんまり拡散しないだろうという観察が大事らしい
-
あんまり小さいコミュニティは考慮しない、次数がでかいのとってくるよ
-
fundamental nodes: 次数がでかくて大事な場所にいる
-
CDH-Kcut
-
CDH-SHRINK
実験
-
θとαとtを色々変えた人工データで見てみる
-
貪欲の改善版?の方がだいたい良いけど、CDHもたまに良い
-
どういうシードが選ばれたかをグラフの図を出して示しているのは、ちょっとおもしろい
-
influence spread: CDH-SHRINK ≈ EGA > CDH-Kcut > DH
-
time: DH > CDH-SHRINK > CDH-Kcut > EGA
KAIS influence maximization
2014-01-08 18:13:35 (Wed)
最終更新:2014年01月08日 18:13