Efficient influence spread estimation for influence maximization under the linear threshold model
-
Zaixin Lu, Lidan Fan, Weili Wu, Bhavani Thuraisingham and Kai Yang
-
Computational Social Networks 2014
概要
-
LTモデルの影響拡散を厳密or精度良く計算
-
4hop以内の影響について厳密計算
-
>4hopはRandom walkで近似
性質
-
$$ \sigma(S) = \sum_{\pi \in P(S)} \prod_{e \in \pi} w(e) + |S| $$
-
P(S) = S内の頂点から出てる単純経路
-
シードは入辺を選ばないからSからSへは到達しない
-
各ランダムグラフ上で各v∈Sから出る部分グラフは木でかつ他の木と交差しないから∑をとれる
-
σ_T(v): T hop以内のvの影響拡散
-
Tが小さい例
-
σ_0(v) = 1
-
σ_1(v) = σ_0(v) + Σ_{u ∈ N+(v)} w_uv
-
一般には
T≦4の計算
アイデア
-
C_l(v) = vから始まり閉路を含む長さlの経路の集合
-
正確には後で定義する奴で
-$$ \varrho_T(v) = \sum_{2 \leq \ell \leq T} \sum_{\pi \in C_\ell(v)} \prod_{e \in \pi} w_e $$
-
$$ \sigma_T(v) = \sigma_0(vv) + \sum_{w \in N^+(v)} w_{vw} \cdot \sigma_{T-1}^{V-v}(w) $$
-
$$ \sigma_{T-1}^{V-v}(w) $$ = vを抜いたグラフでの$$ \sigma_{T-1}(v) $$の値
-
※↑は決してvに到達する経路を数え上げないので等式が成立
-
$$ = \sigma_0(v) + \sum_{w \in N^+(v)} - \varrho_T(v) $$
何をしているか?
-
グラフ全体の各頂点について入辺を確率的に選ぶ
-
σ_{T-1}(w)にカウントされているある経路のがvを含んでいるとマズイ
-
そういうのをρで除去する
ρの計算
-
補題: T≦4なら$$ \varrho_T(v) $$はO(Δ^2)で計算可能
-
$$ \varrho_T(v) = \sum_{2 \leq \ell \leq T} \sum_{3 \leq \ell' \leq \ell+1} \sum_{\pi \in C_{\ell}^{\ell'}(v)} \prod_{e \in \pi} w_e $$
-
$$ C_\ell^{\ell'}(v) $$: vから始まる長さlの経路であってl'番目がvの閉路を構成する
-
$$ \sum_{\pi \in C_\ell^{\ell'}(v)} \Pr[\pi] $$を計算したい
-
長さ4ならば以下の3種類
-
(Ⅰ) A→B→A→D→C
-
(Ⅱ) A→B→C→A→D
-
(Ⅲ) A→B→C→D→A
-
※A→B→A→B→Cみたいなのはいいのか?
-
B→A→Bの時点で除去される(左へと経路を伸ばすことに注意)
-
計算方法
-
(Ⅰ)
-
長さ2の単純経路と長さ2の閉路を前計算
-
↑がv以外の共通部分を持たぬようにする
-
実際には無効なパターンを引く
-
(Ⅱ)
-
(Ⅲ)
-
O(nΔ^2)時間で全頂点のσ_4(v)が計算できる
T≧5の近似計算
-
Monte-Carloシミュレーションは遅いので,乱択アルゴリズム
-
$$ \sigma_T(v) = \sum_{\pi \in P_T(v)}\prod_{e \in \pi} w_e $$
-
$$ = \text{arg}_{\pi \in P_T(v)} \left[ \prod_{e \in \pi} w_e \right] \times |P_T(v)| $$
-
単純経路P_T(v)の数え上げがダルい
-
任意の経路を数え上げて[πが単純]Pr[π]を計算すると考える
-
↑の数え上げは漸化式書けば簡単
-
経路の総数が分かっていればランダムサンプリングして平均っぽいことをすればOK
まとめ
-
せやな,という結果
-
4の根拠とは…
-
多分そういう研究あるはずだけど,特に言及されていなかったなぁ
-
オープンアクセスだし
影響拡散 影響最大化 情報拡散
2015/04/12 23:53
最終更新:2015年07月18日 02:01