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→2 wp P_12
-
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っぽいんだが…
-
比較対象が無いんだが…
-
包除原理を使って新しい計算方法を考えたよ!ってのが評価されたのかな
-
比較対象が無いからだけど、グラフもあんまり大きくない
CIKM influence maximization
2013-11-05 00:34:22 (Tue)
最終更新:2013年11月05日 00:34