Maximizing the Extent of Spread in a Dynamic Network
-
Habiba, Tanya Y. Berger-Wolf
-
? 2007
概要
-
動的ネットワークでinfluence maximizationやるお!
問題定義
-
Dynamic Network
-
G_t = (V_t, E_t)の列
-
特定の時点のものだから,辺は消えたりする
-
Independent Cascade Modelの拡張
-
uが時刻tでactiveだったら(u_t, v_t)なv_tを伝播確率でactivate
-
成功したらvは時刻t+1でactiveになる
-
一旦activeになったらずっとactive
-
他の時刻で辺があったらまた試行できる
-
σ(A): 最終時刻でactiveな頂点数
-
Linear Threshold Modelも似た感じ
-
基本的な性質は成り立つの貪欲すうr
実験
-
最適解と貪欲アルゴリズムの比較
-
dynamicの時とstaticの時の比較
-
dynamicの方が値を大きくするのは難しいね
-
staticとして求めるとdynamicでさらに悪くなる
-
dynamicとstaticは違うのはちゃんとやらんといけない
まとめ
dynamic graphs influence maximization
2014-05-22 17:14:14 (Thu)
最終更新:2014年05月22日 17:14