Efficient algorithms for influence maximization in social networks - todo314 @ ウィキ

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

1. グラフをコミュニティに分割
2. 各々で大事な頂点を選ぶ
3. 影響が被らないように（損するから）選ぶ
4. 元のグラフに対応する頂点を選ぶ

• コミュニティ外にはあんまり拡散しないだろうという観察が大事らしい
• あんまり小さいコミュニティは考慮しない、次数がでかいのとってくるよ
• 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)