Profit Maximization over Social Networks

Profit Maximization over Social Networks

  • Wei Lu, Laks V.S. Lakshmanan
  • ICDM 2012

概要

  • バイラルマーケティングで得られる利益についてちゃんと考えよう
  • LTモデルを拡張するよ
  • 非活性→活性→採択
    • [価格<評価]なら活性→採択に遷移
    • 採択の段階で初めて利益発生
  • (利益 - シードへの費用)が評価関数
  • シードと価格の設定を求めたい

Linear Threshold Model with User Valuation and Its Properties

モデル・問題定義

  • v_i: ユーザiが感じる商品への価値
    • 確率分布から抽出
  • p_i: 相場
  • c_a: 獲得コスト
    • シードにするためのコスト
  • 非活性→活性
    • 採択近傍の重み和≧閾値
  • 活性→採択
    • p_i≦v_i
  • 利益関数π(S,p): 2^V×[0,1]^|V|→R
    • 後でちゃんと定義する

簡単な場合

  • v_i=pに固定
  • シードに対してp_i=0,それ以外はp_i=p
    • pは固定しちゃう
  • π(S) = p×(σ(S)-|S|) - c_a|S|
  • ↑これでもNP-hard,しかも非単調・劣モジュラ
  • ゲインが正の間貪欲に撮り続けると(1-1/e)OPT-Θ(|S|)くらいになる

一般の場合

  • S,pがgivenの時,
  • ap(u_i): u_iの採択確率
  • ip(u_i): u_iの活性確率
  • π(u_i): u_iから得られる期待利益
    • シードでないなら p_i(1-F_i(p_i)),シードなら p_i(1-F_i(p_i)) - c_a になる
  • 1項目は劣モジュラ,2項目は線形なので劣モジュラ,で足せば劣モジュラ,ただし単調とは限らない
  • 利益は単調で無いのでシードの個数は制限無し

アルゴリズム

  • さっきの貪欲アルゴリズムを使う
  • pをどう決めるかが問題
  • 3つの方針を建てたよ
  • All-OMP
    • その頂点が採択したときの最大の利益
  • FFS
    • もうちょっと工夫
    • PAGE
    • 上2つはグラフ構造を考えていないのでもっと工夫
    • シミュレーションを中でちゃんとするっぽい
    • CELFテクも入れちゃう

実験

  • モデル
    • 実際のデータから得られるそれっぽい重み付け
    • {0.001, 0.01, 0.1}
  • ベースラインとの比較
  • 価格がどうなったかとか
  • あまり大きくないけど数時間とかかかる
    • しょうがないね

まとめ

  • 割りとまともっぽい
  • 単調じゃないのは大変

ICDM 影響最大化 情報拡散 情報拡散モデル

2014-05-06 14:34:46 (Tue)

最終更新:2014年05月06日 14:34