Computing and maximizing influence in linear threshold and triggering models - todo314 @ ウィキ

Computing and maximizing influence in linear threshold and triggering models

• Justin T. Khim, Varun Jog, Po-Ling Loh
• NIPS 2016

概要

• 影響拡散の上下限を新たに作ったよ！
  • LTモデルとTriggeringモデル
• 下限は単調劣モジュラなので、最大化できて良い解になる

主結果

LTモデル

• 上限 $$ \leq |A| + \mathbf{b}_{\bar{A}}^\top (\mathbf{I}-\mathbf{B}_{\bar{A}\bar{A}})^{-1} \mathbf{1}_{\bar{A}} $$
  • An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ...と大体同じ
• 下限 $$ \geq \sum_{0 \leq k \leq m} \omega(P_A^k) $$
  • $$ \omega(W) = \sum_{w \in W} \omega(w) = \sum_{w \in W} \prod_{e \in w} b_e $$
  • $$ P_A^k $$：$$A$$から$$\bar{A}$$までの長さkの経路全体
  • Efficient influence spread estimation for influence maximization under the ...と一部かぶっている
• 最悪時には全然駄目、下限=1.5、上限=(n+2)/4
• 適当に仮定を置いて下限/上限をバウンドしようとしている

Triggeringモデル

• 何かそれっぽいやつ

その他性質

• 下限はすごく特殊な場合（近傍しか見てない）には、単調劣モジュラ

実験

• 目的：上下限がそれ程タイトか？貪欲アルゴリズムはどれくらい良いか？
• データ：Erdős–Rényi、Preferential attachment、Gridで全て小さめ
• シードの選び方はシミュレーション回数が全体的に雑

まとめ

• 見所なし

NIPS 影響拡散 影響最大化

2017/10/02