Tight Bounds for Influence in Diffusion Networks and Application to Bond ... - todo314 @ ウィキ

Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology

• Rémi Lemonnier, Kevin Scaman, Nicolas Vayatis
• NIPS 2014

概要だけ

• 情報拡散のサイズの期待値のバウンドが欲しい
• ネットワーク科学方面の結果は辺確率が一様の場合
• 拡散モデル
  1. 離散時間情報カスケード
     • いつもの
  2. 連続時間情報カスケード
     • 遅延時間の分布、T→∞だけ考える
  3. ランダムグラフ
     • 到達可能なら拡散
  • 無限時間後なので、ぶっちゃけ同じ（補題1）
• Hazard matrix
  • $$ \mathcal{H}_{ij} = -\ln(1-p_{ij}) $$で定義
• これのスペクトル半径を気にしていく
  • $$ \rho(M) = \max_i \lambda_i $$
  • $$ \rho_c(A) = \rho(\frac{\mathcal{H}(A)+\mathcal{H}(A)^\top}{2}) $$
    • 二次形式でなんかいい感じに表現できる
• 命題1とその系1
  • 任意の頂点集合に関する影響拡散の上限
  • $$ \rho_c(A)<1 $$なら$$ \sigma(A) = O(\sqrt{n}) $$
• 命題2とその系2
  • ランダムなn0頂点集合に関する影響拡散の期待値の上限
  • $$ \rho_c(A)<1 $$なら$$ E[\sigma(A)] = O(1) $$
    • ※なんか数式をよく見ると怪しい気もするが気にしないことにする 他のモデル、限定したグラフでも解析結果を出しているけど省略
• 実験
  • スペクトル半径$$ \rho_c(A) $$ vs. $$ \sigma(A) $$を―上限の曲線付きで―プロットしてみる
  • そこそこ良い？
  • ネットワークによっては（preferential attachmentとか2D grid）微妙

まとめ

• なんとも言い難い結果
• そこまでタイトな上限が出せるとは思っていないので、しょうがない。

NIPS 影響最大化 情報拡散

2017/07/28