独立カスケードについて思ったこと

[Kempe-Kleinberg-Tardos. KDD'03]による影響最大化の定式化の際に情報拡散モデルとして独立カスケードと線形閾値モデルが採用・提案された．

インパクトが大きく，扱いやすかったので，特に独立カスケードは拡張・変種が沢山生み出されている．
一方で，拡散の大きさが実際の分布（例えばTwitterのリツイートの大きさ）とは違うと指摘されていることもある．具体的には，確率が高いと双峰性っぽい感じになる．
自分の手法[Ohsaka-Akiba-Yoshida-Kawarabayashi. AAAI'14]はこの性質を（部分的に）利用しているのだけれど，ちょっと気になるので調べてみた．

独立カスケード

  • 入力: 辺確率つきグラフG=(V,E,p)，シードs∈V
    • 一般にはシード集合S⊆Vで良い
  • 出力: σ({s}) = E[|Rs|]
    • Rs := sをシードとして独立カスケードをシミュレートした時のvの拡散の大きさを表す確率変数
  • 独立カスケードのシミュレーション
    1. キューにsを入れる
    2. キューが非空な限り
      1. キューから頂点uを出す
      2. uの出近傍vについて
      3. 確率p_uvで次を実行
        1. vが未訪問ならvをキューに入れる
  • ポイントは各辺は高々一回しか見ないということ
    • つまり，確辺eを確率p_eで残した時のランダムグラフ上でsから到達可能な頂点集合と等しい

やったこと

  • 各辺確率を色々変えた時のある頂点の影響の広がり|Rv|の分布を見てみる
  • 確率設定
    • UC(P)モデル: p_e = P
      • 一様に設定する簡単なモデル
    • WC(P)モデル: p_uv = P/indeg(v)
      • 入次数が期待値1なので，線形閾値を模擬している（皆大好き）
  • データセット
  • ランダムに選んだ頂点から割りと影響力が高いものを事前に一つ選び，1,000,000回シミュレーションして，Rvの分布をプロットしてみた結果
    • UC(0.01): 確率が小さすぎるので，特に何も起こらない．
    • UC(0.1): パット見べき分布．ちょっとは広がっているけれど，ネットワークの中心部には到達していない．
    • UC(0.2): はっきりと拡散の大きさが二分されている．ネットワークの中心部に到達するか否かが分かれ目．拡散が小さい方はUC0.1に対応していることが分かる．
    • WC(1): UC(0.1)に似てる．中心部にやはり到達していない？
    • WC(2): キモい．UC(0.2)とかに比べたら，ギャップが滑らか．中心部の方が確率が低い（∵高次数）ので，到達すれば「爆発」というわけでもない．
    • WC(4): ※これだけlog-logスケールでない．とってもわかりやすい形．おそらく低次数の部分の確率が十分に高いので，あとは中心部が爆発するか否かだけが支配的．
  • 拡散が凄く大きくてもべき分布っぽくできるかは少し謎（今回の場合10,000オーバー）．
  • 与えられた出現頻度を再現する辺確率設定を復元する，とかは頑張れば出来るのでは…？