IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks - todo314 @ ウィキ

IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks

• Mo Li, Zhenjiang Li, Longfei Shangguan, Shaojie Tang, and Xiang-Yang Li
• TPDS 2014

概要

• influence maximizationのGPUを取り入れたよ
• 既存手法の60倍速くなったよ

IMGPU

Bottom-Up Traversal Algorithm (BUTA)

• 元のグラフから沢山ランダムグラフを作る
• 各頂点のレベルを定義
  • 末端までの最長距離
• レベルで並列化するよ
• SCC内は全部同じなのでつぶすよ
• σ_S(u) = Σ_{v∈out(u)} σ_S(v) + w(u) - overlap(out(u))
  • overlapは各頂点から到達可能な頂点の重複部分
• 全体でO(kRm)
  • ホントかいな…
  • MixGreedyはCohenのアルゴリズムを使っているが，こっちは正確に求めるらしい
  • Appendixがあるらしいのでそのうち読む

GPUでの実装

• 辺をどう持つかまで言及
• かなり細かく書いてあるけれど専門的なので分からない

実験

• 比較手法
  • 本論文: BUTA（普通に実行），IMGPU，IMGPU_O（さらに最適化）
• データセット
  • Twitterが大きい，|V|=11M，|E|=85M
• 確率設定
  • p=0.01
• influence spread
  • ヒューリスティクス系のσは全然駄目
• 実行時間
  • Twitterでは，IMGPU(_O)は2~3万秒位？
  • IMGPUはBUTAに比べて10倍位しか（？）変わらない
    • 結構デカイのかな？
  • PMIAが普通に動いている
    • pが小さいからなあ
• 色々入れた最適化のそれぞれの効果を実験

まとめ

• 並列・分散のジャーナルだし，GPUで頑張れば通るのかあ
• BUTAがいまいち分からなかった
• p=0.1でやって欲しい

TPDS influence maximization

2014-03-19 23:37:34 (Wed)