On Influential Nodes Tracking in Dynamic Social Networks - todo314 @ ウィキ

On Influential Nodes Tracking in Dynamic Social Networks

• Xiaodong Chen, Guojie Song, Xinran He, Kunqing Xie
• SDM 2015

概要

• 動的グラフでの影響最大化
• 今のシードを交換ヒューリスティック
• 影響力の評価は上限ベースの手法も使って枝刈り

提案手法

• [Nemhauser-Wolsey-Fisher. '78]の交換ヒューリスティック
  • 局所改善で1/2近似
• あまりシード集合が変わらないはずだからという観察
• $$ S' = S-v_s+v^* $$
  • $$ v^* \in V \setminus S $$: 一番上昇する奴
  • $$ v_s $$: 上限使って一番良さそうなの

1. |S|回ループ
   1. $$v_s^*$$: 上限使って一番良い奴
   2. 遅延評価＋適当な打切，でSを更新
      • その場でσを計算しなおしたりする
   3. 上限を更新

• 近似保証は消える

上限の計算

• ICDM'13の手法を頑張るらしい
  • 実は一番頑張っている所？

実験

• (n, m): (5M, 12M), (30K, 300K), (20K, 100K)
  • 最大はまぁそこそこ小さい
• データセットの作り方がちょっと違う（時間窓で区切ってる）
• 辺確率: (入次数)$$^{-1}$$ （だけ． (ﾟДﾟ)ﾊｧ?）
• 実行時間と影響力
  • 結構速いのか？
• スケーラビリティ
• 類似度 vs. 更新時間
  • tとt+1のJaccard係数を計算; 変化が小さい方が速い
• 上限の計算手法の比較
  • 提案手法の方がタイトに見積もれている

まとめ

• ヒューリスティックは面白いけれど，手法はそんなに．

SDM 動的グラフ 影響最大化

2016/02/15