CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social ... - todo314 @ ウィキ

CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social Networks

• Amit Goyal, Wei Lu, Laks V.S. Lakshmanan
  • 何かよく見るな名前
• WWW 2011

CELF++

• CELFを速くしたよ！！！
• 頂点uは→を持つ <u.mg1, u.prev_best, u.mg2, u.flag>
  • mg1: Sに対するマージン
  • prev_best: u以前に見た中でbest
  • mg2: S+prev_bestに対するマージン
  • flag: 最後にmg1が更新された時刻
• どうやって早くなるの？
  • とりあえず、↑の値を全部計算済みだとする
  • 最後に選ばれたシードをtだとすると、
  • uを見た時に、もしt=prev_bestだったら、u.mg1は再計算せずに今のu.mg2を使えば良い
  • ↑が成り立たなかったら、prev_bestは今のところ一番mg1のでかいのにして、mg1とmg2を同時に計算する
  • BFSだから、mg2の後にmg2を計算すると効率が良い
• 実験結果
  • 2倍位早くなったよ（＾ω＾ ）…

まとめ

• ポスター発表だってお…

WWW influence maximization

2014-01-22 23:12:00 (Wed)