Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret - todo314 @ ウィキ

Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret

• Çigdem Aslay, Wei Lu, Francesco Bonchi, Amit Goyal, Laks V. S. Lakshmanan
• VLDB 2015

概要

• ソーシャルネットワーク上で広告マーケティングをしたい
• 今までのは伝播を未考慮
• ホスト、広告主、ユーザの関係をうまく定式化
  • ホスト…自分の利益を最大化するように、ユーザに広告を配置
  • 広告主…エンゲージメント毎にホストへ（予算の範囲で）金を支払う
  • ユーザ…タイムラインに大量の広告が流れてくるとやだ
• 貪欲アルゴリズム…regretに関する保証

問題定式化

• 広告$$i$$, トピック$$z$$
• 広告iを流した時の辺確率 $$ p_i(u,v) = \sum_{z \in [Z]} \gamma_i^z \times p^z(u,v) $$
  • $$ \gamma_i^z $$ ＝広告iのトピック分布
  • $$ p^z(u,v) $$ ＝トピックzの辺確率
• 広告iを見たときにシードuがクリックする確率 $$ \delta(u,i) = \sum_{z \in [Z]} \gamma_i^z \times \delta p^z_H(u) $$
  • $$p^z_H(u)$$はgiven
• 広告iに関する期待収入 $$ \Pi_i(S_i) = \sigma_i(S_i) \cdot cpe(i) $$
  • $$ \sigma_i(S_i) $$: E[クリック数]（シードはδ(u,i)の確率でクリックして拡散開始）
  • $$ cpe(i) $$: エンゲージメント毎に支払う費用
• 目標と制約
  1. 広告主iは予算$$B_i$$以内に抑えたい
     • 逆にホストは期待収入を$$B_i$$に近づけたい…不足・余剰分はregret
  2. ホストはあまり大量の人に流したくない
  3. 各ユーザのタイムライン上の出現回数 $$ \kappa_u $$
  • 目的関数 $$ \mathcal{R}(S) = \sum_{i} \mathcal{R}_i(S_i) $$
    • $$ \mathcal{R}_i(S_i) = |B_i - \Pi_i(S_i)| + \lambda |S_i| $$
    • 制約 $$ |\{ S_i \in \mathcal{S} \mid u \in S_i \}| \leq \kappa_u $$

アルゴリズム

• 貪欲アルゴリズム…超頑張って解析
• でも遅い
• RISを導入…頑張って精度保証

実験

• 色々やりました

まとめ

• 設定は結構正しそう
• regretの定式が微妙？

VLDB オンライン広告 影響最大化

2017/09/20