「Simpath: An Efficient Algorithm for Influence Maximization under the Linear ...」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
Simpath: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model
- Amit Goyal, Wei Lu, Laks V. S. Lakshmanan
- ICDM 2011
&tags()
&update()
Simpath: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model
- Amit Goyal, Wei Lu, Laks V. S. Lakshmanan
- ICDM 2011
* LTモデルの性質
- $$ \sigma(S) = \sum_{v \in V} \Upsilon_{S,v} $$
-- Υ_S,v = Sがvを活性化させる確率
- $$ \Upsilon_{s,t} = \sum_{\pi \in \text{Path}(s,t)} \Pr[\pi] $$
-- By definition of the ``live-edge'' model と簡単に言うが…
- ※結局はσ({s})はsを始点とする全ての単純経路の出現確率の総和
- $$ \sigma(S) = \sum_{v \in S}\sigma^{V-S+v}(v) $$
-- 集合を考える場合は種同士が到達可能にならないように部分グラフを制限する
- 証明されたこと
-- $$ \Upsilon_{S,v} = \sum_{u \in S}\Upsilon_{u,v}^{V-S+u} $$
* Simpath-Spread
- 全経路の総重みが知りたい
- 経路は長くなると確率が落ちる
- 近傍だけ見よう！
- 確率がη以下になったら打ち切り
- CELFだけだと（特に最初の反復が）心許ないので幾つか高速化を入れる
** A. 頂点被覆最適化
- $$ \sigma(u) = 1+\sum_{v \in N^+(u)}\sigma^{V-u}(v) $$を利用
- V=C∪(V-C) に分割
-- Cは無向頂点被覆
- 最初の反復で，
- 各v∈Cについて
-- $$ \sigma(\{v\}) $$と$$ \sigma^{V-u}(\{v\}) (u \in N^-(v) \cap (V \setminus C)) $$を計算
-- 再帰しながら上手くできる
- 各u￢∈Cについて
-- v∈N+(u)は必ずCに含まれるので（そうでなければ，Cはは頂点被覆でない），↑の定理の式で計算できる
** B. 先読み最適化
- $$ \sigma(S_i+v) = \sigma^{V-S_i}(v) + \sigma^{V-v}(S_i) $$
-- なので，左辺の第一項を適当なU⊆Vについてまとめて前計算する
* 実験
- |E|<7M
- σの比較
- 計算時間の比較
- メモリ使用量の比較
- 各最適化の効果
- 先読みパラメータの調査
- ηの調査
- 平均hop数の比較
* まとめ
- SimPathとあるから本気で経路を数え上げるかと思ったが違った
&tags
2015/04/13 0:15
