Cost-aware Targeted Viral Marketing in Billion-scale Networks - todo314 @ ウィキ

Cost-aware Targeted Viral Marketing in Billion-scale Networks

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

概要

• 新しい問題 Cost-aware Targeted Viral Marketing
  • ユーザ毎に最初の費用が違う & ユーザ毎に影響させた事による効果が違う
• いい感じにすれば$$ 1-1/\sqrt{e} $$近似が可能
• 効率的アルゴリズム BCT：CTVMにもInfMaxにも適用可能
• LISA [CSoNet'15]の後続

Cost-aware Targeted Viral Marketing

• 費用$$c(u)$$、利益$$b(u)$$、予算$$B$$
• 目的関数：Sの影響した頂点uの利益b(u)の総和
• 制約：$$c(S) \leq B$$
• いわゆるBudgeted Influence MaximizationやTargeted Viral Marketingの一般化

提案手法 BCT

CTVM特有の話題

• サンプリング
  • 頂点利益に重み付けした確率でサンプリングすればOK
  • Coarsening Massive Influence Networksのと同じ奴ね
• シード選択
  • （サンプリング後）次の内、良い方を返す
  1. $$ \frac{F_{\mathcal{R}}(S+v)-F_{\mathcal{R}}(S)}{c(v)} $$で貪欲
  2. $$ F_{\mathcal{R}}(v) $$最強の（制約を満たす）頂点v

RR集合のバウンド

1. $$ \Lambda_L \leq 7.4 \epsilon^{-2} \left[ \ln \delta^{-1} + \ln {n \choose k} + \frac{2}{n} \right] $$
2. 倍々にRR集合を増やし、貪欲算法を走らせる→解S
3. $$ |\mathcal{R}| \cdot F_{\mathcal{R}}(S) \geq \Lambda_L $$なら終了
   • 単一頂点ではないのがLISAとの違い

• 解析は何か頑張っている
  • ICもLTも対応出来る

実験

• 辺確率：というかLTモデルだけっぽい
• 比較手法：TIM, TIM+, CELF++, SIMPATH++

まとめ

• はい。
• 実験設定が微妙

2017/10/01