Threshold Models for Competitive Influence in Social Networks - todo314 @ ウィキ

Threshold Models for Competitive Influence in Social Networks

• Allan Borodin, Yuval Filmus, Joel Oren
• WINE 2010

• 久しぶりの論文記事(ヽ´ω`)

概要

• LTモデルを競合者付きモデルに拡張
• 劣モジュラどころか単調ですらないものもある

Weight-Proportional Competitive Linear Threshold Model

• 頂点vはしきい値θ_vを持つ
• 活性近傍からの重みの和がθ_vになったら活性化
• 状態は3つ: 非活性，活性A，活性B
• 活性Aの近傍の割合:活性Bの近傍の割合で確率的にAかBかに決まる
• S_B=∅なら元のLTモデルと同じ
• 定理
  • 劣モジュラ・単調でない例がある

Separated-Threshold Model for Competing Technologies

• しきい値が2つ: θA_v, θB_v
• 重みの2種類: wA, wB
• 各々でしきい値判定をする
• もし，AかBかのどちらかだけが活性化条件を満たしたらそっちになる
  • AもBも同時に条件が満たされたら等確率でどちらかになる
• 定理
  • 単調だけど劣モジュラでは無い

Competitive Threshold Model with Forcing

• ↑のカスケード終了後，非活性頂点は必ずAかBかを選ぶ
  • 投票とかはこれに該当する
• でも劣モジュラでは無い

近似できる？

• やばい

OR Model

• AとBのカスケードは全く独立に行われる
• R_A, R_B: A/Bを選択した頂点集合
• 各頂点vは確率fA_v(R_A,R_B)でA，fB_v(R_A,R_B)でB，それ以外は非活性を選択する
• 関数に適当な仮定を置くと1-1/e近似が多項式回数でできる

まとめ

• 一杯提案したなあ…

WINE 影響最大化 情報拡散

2014-04-29 22:36:19 (Tue)