How to Influence People with Partial Incentives - todo314 @ ウィキ

How to Influence People with Partial Incentives

• Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, Morteza Zadimoghadam
• WWW 2014

概要

• 今までのinfluence maximizationは二者択一だった
• 実際には中間があるので，そういうモデルを作ったよ
• 分数版は積分版との違い

モデル

積分影響モデル(integral influence model)

• Mossel and Rochの提案
• f_v:2^V→[0,1]
  • 辺を含んだ集合関数
• θ_v∈[0,1]: しきい値
• f_v(S)≧θ_vになったらvがactivated
• Θ=(θ_v)を決めれば最終状態は決定する
• $$ \sigma(S) = E_{\Theta}[ w(S_n^{\Theta}) \mid S_0 = S ] $$
  • θ_v~U[0,1]
  • w: 2^V→R_+
• 最初にactivateするSを決めてσ(S)を最大化したい

分数影響モデル(fractional influence model)

• 上のモデルはどれをactiveにするか否かが明確に分かれているのでダサい
• x∈[0,1]^n
• x_v: vへの影響
• f_v(S)+x_v≧θ_vならvがactivated
• 最初にactiveにする頂点は存在しない←新しい
• S_1={v | x_v≧θ_v}←これが最初
• 積分モデルの上位互換
  • 1フェーズずれるだけと考えればOK
• $$ \sigma(S) = E_{\Theta}[ w(S_n^{\Theta}) \mid \mathrm{we apply direct influences}x ] $$
• これから…
  • σの構造と近似解xの見つけ方

積分モデルと分数モデルの違い

1. しきい値を固定した時には目的関数値がn倍変わる
2. 一様しきい値の時には目的関数値が1-1/e倍変わる

帰着

• 定理1
  • 積分モデルでwとFがnormalized, monotone, submodularならばσもnormalized, monotone, submodular
  • normalizedはσ(0)=0のこと

submodularの拡張した定義

• 定理1を分数モデルに拡張したいね
• δ=1/N
• Δ={0,δ,…,1}
• σの範囲をΔ^nに制限
• normalized: σ(0)=0
• monotone: x≦yならばσ(x)≦σ(y)
  • pairwiseかな
• submodularσ(x+δ_v)-σ(x)≧σ(y+δ_v)-σ(y)
• 定理2
  • 分数モデルでwとFがnormalized, monotone, submodularならばσもnormalized, monotone, submodular
  • ただしΔ^nで離散化
• 証明が驚きの1ページ半
• 定理3
  • 離散化をやめて[0,1]^n上でもOK
• 定理4
  • 離散化した時には解の質が(1-δn)以内に保たれる

DAGS

• GはDAG
• f_v(S)が近傍のw_uvの和だとする
  • 線形モデル
• 定理5
  • σ(x)が超簡単に計算できる

困難さ

• 超適当に紹介
• 定理6
  • 線形（積分/分数）モデルにおいて，σ(S)≧Tが（Sの適当な制約の元で）達成できるかの判定はNP-hard
• 補題7
  • ↑の問題でn^{1-ε}近似がNP-hard
• 定理8
  • 1-1/eより良い近似比を達成するのがNP-hard

実験

• グラフは小さめ|E|=1.2M
• 比較手法
• {積分版,分数版}×{次数,割引}
  • 積分は{0,1}だけど分数は[0,1]で割合を考慮
• 積分ランダム + 分数一様
• 全部ソートするだけなのでnlognオーダー
• 結果: DiscountFracが最良
• 議論: 部分的な割り当てを考慮したほうが良い拡散を引き起こせる

まとめ

• 解析がすごく大変そうだけれどその辺はWWWでは評価されるんかな？
• こっちのモデルの方が頑健性を高くできそう
• ヒューリスティクスじゃないアルゴリズムは作るの大変そう
  • Optimizing Budget Allocation Among Channels and Influencersと関連が…?

WWW influence maximization modeling

2014-03-25 18:15:42 (Tue)