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: 獲得コスト
-
非活性→活性
-
活性→採択
-
利益関数π(S,p): 2^V×[0,1]^|V|→R
簡単な場合
-
v_i=pに固定
-
シードに対してp_i=0,それ以外はp_i=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