A Data-Based Approach to Social Influence Maximization - todo314 @ ウィキ

A Data-Based Approach to Social Influence Maximization

• Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan
• VLDB 2012

概要

• Data-Basedの意味：伝播確率をデータから推定するのではなく、直接σを推定する
• Credit Distribution Modelというモデルを提案
  • NP-hardでsubmodular
  • σ_CDでの最大化が良いし速い！！

何でこんなことになったのか

• いろんなモデルを使って実験してみよう
• weighted cascade model
• trivalency model
• uniform IC model
• EMアルゴリズムベース
  • 学習したよ！
• EM perturbed
• Q1. これらのモデル上で計算した（サイズ50の）seedに共通部分はあるのか？
• A1. あんまりない(´・ω・`)
• Q2. influence spreadの値の予測は正しいかな？
• A2. そうでもない
• もっとちゃんと実データのinfluence spreadを反映するようにしないとダメダメダメ～

Credit Distribution Model

• どういうデータモデル？
  • action aが頂点を伝搬する
    • aはいっぱいある
  • t(u,a): uがaを時刻tにした
  • tで順序を与えれば、DAGが出来る
• Sからuへ経路が存在する確率を見積もる
  • Sからuに伝わるaの個数をa全体の個数で割るだけ

• 最大化したい！
  • 長い証明がある
  • marginal gainを求めるには
    • actionと頂点のループで頑張っている
    • 遅くね？？？
    • アルゴリズムはもっと色々頑張っているっぽい

実験

• influence spread
  • 良いね！
  • 何を元にしたんだ？
  • 真のISは分からんので、誤差が少ない（？）のを選んだ（謎）

• 計算時間
  • 速い（迫真）
  • ぶっちゃけそうでもないように見える
  • ICとかLTのが遅すぎる
  • データサイズ=(a,u,t)の数には比例

まとめ

• 確率見積もるのは実際めんどそう
• でも、尋常じゃなくデータが多い場合は、やっぱり確率計算した方がいいんじゃないか？
• ソッチのほうがデータ少ない気がする

VLDB influence maximization information diffusion modeling

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