Opinion maximization in social networks - todo314 @ ウィキ

Opinion maximization in social networks

• Aristides Gionis, Evimaria Terzi, Panayiotis Tsaparas
• SDM 2013

概要

• 意見を表現するモデル
• 影響最大化のフレームワーク？として問題定式化

導入

• 意見
• ICやLTでは表現できない
• バイナリ状態も微妙
• というわけで，実数の状態をとるよ

問題定義

モデル

• [Bindel, Kleinberg, Oren. FOCS11]に従う
• [Friedkin, Johnsen. 90]も大事
  • Social influence and opinions
• 内部意見 s_i と表明意見 z_i がある
  • z_iはs_iと近傍のz_jに依存する
  • それぞれ[0,1]の実数
  • 0は負，1は正の意見
• 頂点iのコストを定義
  • (s_i-z_i)^2 + Σ_j w_ij(z_i-z_j)^2
  • 自分の信念も考慮しつつ重み付きで周りに合わせる
• c_iを最小化しようとするz_iは計算できる→各頂点が反復で更新→ナッシュ均衡

問題定義

• 頂点集合Tの「z_iを1に固定」し，g(z|T)=Σz_i を最大化したい
• ランダムウォークと関連があるらしい（読んでない）

計算量

• NP-hard，単調，劣モジュラ

提案手法

• ナッシュ均衡の計算
  • 逆行列とか面倒なので，Power Iteration
• 全体としては貪欲アルゴリズム
  • やっぱりquadratic
• ヒューリスティクス作るよ

実験

• よくあるはなし

まとめ

• 実数なのは面白いけれど，行列だなあ，というかよくあるよなあ…

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

2014-09-10 00:53:59 (Wed)