「IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks」の編集履歴（バックアップ）一覧はこちら

「IMGPU: GPU-Accelerated Influence Maximization in Large-Scale Social Networks」(2014/03/19 (水) 23:37:34) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* 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でやって欲しい

&tags()

&update()