Simpath: An Efficient Algorithm for Influence Maximization under the Linear ... - todo314 @ ウィキ

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とあるから本気で経路を数え上げるかと思ったが違った

ICDM 影響最大化

2015/04/13 0:15