Influence Maximization in Big Networks: An Incremental Algorithm for ... - todo314 @ ウィキ

Influence Maximization in Big Networks: An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation

• Weixue Lu, Peng Zhang, Chuan Zhou, Chun-Yi Liu, Li Gao
• IJCAI 2015

概要

• 小さい部分グラフに分割する
  • 頂点を共有しうるが辺は互いに素
• 挑戦: 部分グラフ間のシミュレーションが重なる

提案手法

• M=シミュレーション回数
• N=分割個数
• $$ (V_i)_i $$: Vの被覆
• $$ (E_i)_i $$: Eの分割
• X_r = コインフリッピング結果rを表す01値ベクトル
• $$ G_i $$からスナップショット$$ X_1^{(i)}, \ldots, X_r^{(i)}, \ldots, X_M^{(i)} $$
  • $$ X_r = \bigoplus_{1 \leq i \leq N} X_r^{(i)} $$
• $$ \sigma(S) = \sum_{r^{(1)}} q(r^{(1)}) \cdots \sum_{r^{(N)}} q(r^{(N)}) |N(S;X_r)| $$
• 各部分グラフ1,…,Nについていくつか生成すると，その全ての組合せを考慮できる

計算方法

• $$ \mathcal{C}_j^{(i)} = \{C_{jk}^{(i)}\} $$
  • $$C_{jk}^{(i)}$$ = i-th部分グラフに関するj-thスナップショットのk-th SCC
• 結び
• 2列のスナップショットに対して↓のような操作を実行
  • $$ \mathcal{C}_1 = \{C_{11}, C_{12}, \ldots, C_{1\alpha_1}\} $$
  • $$ \mathcal{C}_2 = \{C_{21}, C_{22}, \ldots, C_{2\alpha_2}\} $$
  • $$ G_1 \oplus G_2 = (V_1 \cup V_2, E_1 \cup E_2) $$
  • 被っていたら併合，被っていないなら別にする
  • (#スナップショット)^2 = M^2 個のスナップショットができる

影響力推定

• (#スナップショット)^(#部分グラフ) = $$ M^N $$ 個のスナップショットが出来る
  • 指数的なので多すぎ
  • 一部だけ選びたい
  • i.i.d.だと良い
• 普通の推定: $$ \frac{1}{M}\sum_{1 \leq i \leq M} g_{i,i,\ldots,i}(S) $$
• 全部i番目スナップショットの代わりにちょっと変えると精度が上昇

実験

• |E|≦1M
• p_e = 0.01
• 影響最大化が速くなったよ
  • PMCと似ている結果

まとめ

• 手法は微妙そうだけど，アイデアは良い
  • シミュレーション数を劇的に抑える可能性がある
• 実験のグラフが小さい
  • 100M頂点（アブスト）とは何だったのか…