Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in ... - todo314 @ ウィキ

Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks

• Hung T. Nguyen, My T. Thai, Thang N. Dinh
• SIGMOD 2016

概要

• TIM+やIMMより速い影響最大化アルゴリズムを作りました
• RR集合のサンプル数が最小だよ！

枠組み

• 2つの条件
  1. $$ \Pr[\widehat{\mathsf{Inf}}(S_k) \leq (1+\epsilon_a)\mathsf{Inf}(S_k)] \geq 1-\delta_a $$
  2. $$ \Pr[\widehat{\mathsf{Inf}}(S_k^*) \geq (1+\epsilon_b)\mathsf{OPT}_k] \geq 1-\delta_b $$
  • ただし、$$ \delta_a+\delta_b \leq \delta, \epsilon_a+(1-1/e)\epsilon_b \leq \epsilon $$
• 閾値$$ N(\epsilon_a, \epsilon_b, \delta_a, \delta_b) $$個以上RR集合を生成したらこの条件達が成立する
  • TIMとかIMMはそんな感じで解釈できる
• Type-1 minimum threshold: SSAはこっち
  • $$(\epsilon_a, \epsilon_b, \delta_a, \delta_b)$$が固定の元で最小の$$ N^1_{\min}(\epsilon_a, \epsilon_b, \delta_a, \delta_b) $$
• Type-2 minimum threshold: D-SSAはこっち
  • $$ N^2_{\min}(\epsilon,\delta) \equiv \min_{\epsilon_a, \epsilon_b, \delta_a, \delta_b} N^1_{\min}(\epsilon_a, \epsilon_b, \delta_a, \delta_b) $$
  • 最良な4つ組を選ぶ

提案手法

Stop-and-Stare Algorithm (SSA)

1. 今の$${\cal R}$$でMaxCoverを解く→S
2. if Sの被覆の大きさが十分ある
   1. 別のRR集合$${\cal R}'$$をサンプルしてInfを推定
   2. $${\cal R}$$での推定値>(1+ε1)(別のRR集合$${\cal R}'$$での推定値)ならSを返す
3. $${\cal R}$$中のRR集合を倍にする

Dynamic Stop-and-Stare Algorithm (D-SSA)

• $$(\epsilon_a, \epsilon_b, \delta_a, \delta_b)$$の選択が異常に複雑化
  • 会議版、ArXivで色々と違う
• どちらも、定数倍だけthresholdより悪い（らしい）

実験

• 辺確率／重み：1/入次数「だけ」
• 比較手法：D-SSA, SSA, IMM, TIM+, TIM, CELF++

まとめ

• はい。

SIGMOD 影響最大化

2017/10/02