Efficient influence spread estimation for influence maximization under the ...

Efficient influence spread estimation for influence maximization under the linear threshold model

$$ \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
一般には
- DFS: O(Δ^T)

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≦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の閉路を構成する
  - (1)v→…→(l')v→…→(l)t
$$ \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(Δ^3)で計算可
(Ⅲ)
- A→B→C→B→Aみたいなのは避けるように工夫
O(nΔ^2)時間で全頂点のσ_4(v)が計算できる

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

2015/04/12 23:53

タグ：

影響最大化影響拡散情報拡散

最終更新：2015年07月18日 02:01