Probabilistic Solutions of Influence Propagation on Networks

Probabilistic Solutions of Influence Propagation on Networks

  • Miao Zhang, Chunni Dai, Chris Ding, Enhong Chen
    • 色々いるし名前を知らん
  • CIKM 2013

概要

  • 新しいinfluence spreadの計算方法
    • 包除原理?
  • 実験もしてオリジナルより速くなったよ!

Exact influence spread

  • n=3,4,5について、頑張ってinfluence spreadを厳密計算する

3頂点について

  • 1がseed
  • パターンを全部考えて、2、3がactiveになる確率を求めた
  • でも、もっと簡単にできる
  • 1から2がactiveになるには…
    1. 1→2 wp P_12
    2. 1→3→2 wp P_13*P_32
  • ただし、この2つはindependentでないので包除原理をする
  • $$ \pi_2 = P_{1 \rightarrow 2} + P_{1 \rightarrow 3 \rightarrow 2} - P_{1 \rightarrow 2}P_{1 \rightarrow 3 \rightarrow 2} $$
  • これは頑張って計算したのと同じ

4頂点について

  • 1->2と1->3->4->2しかない(図のグラフでは)

包除原理

  • DAGと仮定する
    • かなり強い仮定だなあ…
  • π_v: vがactiveになる確率
  • 定理1
  • π_vは、vの入近傍N_vのactivation probabilityとP_uvを使って表せる
    • DAGだからね♡
    • 近傍の内少なくとも1つから、なので、π_u*P_uvに関する包除原理になる

1ノードについて

  • 補題2
  • $$ \pi_v^{(i+1)} = \pi_v^{(i)} + (1-\pi_v^{(i)})\sigma_{u_{i+1}} $$
  • σはそのノードがactiveになり、vをactivateする確率
  • 反復してれば正しくなるらしい
  • この式はちゃんと定理1の式に一致している

全体のノードについて

  • $$ \pi_v^{(i+1)} = F(\pi_{{\cal N}_v}^{(t)}) $$
  • を繰り返して定常状態を出す、Fは上の式に相当
  • 前との差がδ以下になったらおしまい
  • DAGじゃない時はおかしいことも示しているけど、何か実験では上手くいったらしい

アルゴリズム

Greedy Method 1

  • 各頂点をseedとした時のactivation probを出す
  • σ(v)の高い順にk個返す

Greedy Method 2

  • marginal influenceを求める
  • 定常状態の行列(iをseedとした時にjをactivateする確率)
  • すでにseedがSの時にiを追加してそれぞれの確率がどうなるか更新する
  • 1-(1-P_S)(1-P_i)要素ごとにこれを計算するみたいな感じ

Incremental Search Strategy

  • k個とってk個追加♪
  • k個とるのが大きい順なんだがこれでいいのか?
  • 実験ではk=[1,2,3]

実験

  • データセット
    • (6K, 20K)と(7K, 100K)
    • 小さいなあm9(^Д^)プギャー
  • 比較対象
    • ランダム、次数、平均距離
    • Greedy 1+Incremental、Greedy 2+Incremental
  • Monte-Carloとの比較
    • 適当にソートしてプロット、いいんじゃないですかね
  • influence spreadの比較
    • Monte-Carlo(20000)とほぼおなじ
    • Inc 2、Inc 1、後はゴミ
  • 計算時間
    • Monte-Carloより大体10^4倍速い
    • 速い(確信)

まとめ

  • Naiveでもいいから時間計算量出さんのか?
    • n^2かかっているように見える
    • Greedy 1なんかは7000^2+αだから速いのか…
  • これって、IRIEに似てる?
  • Greedy Method 1の選び方はIRっぽいんだが…
  • 比較対象が無いんだが…
    • Wei Chenとかのを引用はしている
  • 包除原理を使って新しい計算方法を考えたよ!ってのが評価されたのかな
  • 比較対象が無いからだけど、グラフもあんまり大きくない

CIKM influence maximization

2013-11-05 00:34:22 (Tue)

最終更新:2013年11月05日 00:34