Scalable and Parallelizable Processing of Influence Maximization for ... - todo314 @ ウィキ

Scalable and Parallelizable Processing of Influence Maximization for Large-Scale Social Networks

• Jinha Kim, Seung-Keol Kim, Hwanjo Yu
  • 浦項（ぽはん）工科大学校
• In ICDE 2013

概要

• 並列化可能なアルゴリズム
• 競技相手はPMIA
  • 質はCELF並、PMIAより良い
  • 速度はPMIAより速い

提案手法

• Independent Path Algorithm(IPA)
• 経路を指定したらそれを使う確率は全部かければ良い

1. グラフがもらえた
2. 有るノードからtraverseして木っぽくパスを広げる（同じ頂点がいくつかある）
   • しきい値θ未満になった or 閉路にあたったら打ち切り
3. もっかいまとめる（同じ頂点がいくつかある）

• σ(v)は、vからいけるやつについて、各々確率を足す（+1は自分
• v->uの確率は、1-Π[1-ipp(p)]
  • pは↑ので計算されるであろう経路達
• マージンはどうするか
  • 頑張る…？

並列化

• 3フェーズ

1. traversing
   • traverseを一気に
2. re-organizing
   • influence pathをどうにかする
3. updating
   • マージンを求める

実験

データセット

• LiveJournalとかDBLPとか

比較対象

• CLEF、PMIA、IPA、とか

実験結果

• しきい値
  • 実行時間 vs. σとすると、ぐおっといってまたぐおっといく

実行時間

• LiveJournal で200sくらい
  • やばお。
• しかも、seed set sizeの影響は小さい
  • PMIAはでかい

influence spread

• 思ったほどよくない
• GreedyにはStanfordとかで優位に負けている
• LiveJournalとか余裕で勝てんじゃね？？？

並列化の効果

• 1~8コア
• 割りといい感じ何ですか？
• 8コアで3~5倍

まとめ

• 結局PMIAとそんなに変わらないような…
• へんなデータ構造の構成はまともっぽくなった？
• 簡単な並列化でどかっとタイトルにできるなら自分もしようかなあ…

ICDE influence maximization parallel computing

2013-10-23 02:33:16 (Wed)