Influence Maximization in Social Networks When Negative Opinions May Emerge ... - todo314 @ ウィキ

Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate

• Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincon, Xiaorui Sun, Yajun Wang, Wei Wei, Yifei Yuan
• SDM 2011

概要

• 商品の質が低かったらdisる人も出るよねーをモデル化
  • 質をパラメータに含めたNegative Opinion付き
• positiveな人数が目的関数ならsubmodularは保たれる
• 速い手法を作って実験してみたよ

Independent Cascade Model with Negative Opinions

• 状態は3つ，inactive，positive，negative
• 最初にシードをactiveにして，確率qでpositive，1-qでnegative
• positiveが近傍をactivateするときには，確率qでpositive，1-qでnegative
• negativeが近傍をactivateするときには，常にnegative
• activeになったら状態は変わらない
• かなり悲観的な設定
• 目的関数はpositiveな頂点数の期待値

シチュエーション

• ネガティブな意見は強い
• 商品に欠点があったらネガティブになる
• ネットワーク科学的な根拠を色々と持ちだしている
• 悲観的な感じなら納得

性質

• monotoneかつsubmodular
• かなり非自明に感じる
• とりあえずO(knmR)貪欲はできる
• 提案手法ではMIAを拡張している

Quality Sensitivity in Influence Maximization

• "universally good enough"なquality factor q*はあるか？
• 無い
• この辺は正直良くわからん
• O(√n/k)とからしい…

実験

• 設定とかは普通
• qを変えると線形より早くσが上昇する感じ
• 主張: 質=qを高く保つのが大事だね

モデルの拡張

• quality factorを頂点毎
• 伝播確率をpositive / negativeで変える
• 遅延
• 目的関数を変える, e.g., positiveとnegativeの差とか比

まとめ

• 手法は例のごとく謎だが，他は割りと面白い？

SDM influence maximization modeling

2014-03-15 05:48:43 (Sat)