On Approximation of Real-World Influence Spread

On Approximation of Real-World Influence Spread

  • Yu Yang, Enhong Chen, Qi Liu, Biao Xiang, Tong Xu, Shafqat Ali Shad
    • 中国科学技術大学
  • In PKDD 2012

概要

  • influenceの計算を近似+反復計算で
  • p_v~Σp_uv*p_u.これをガウスザイデル
  • p_v=1-Π(1-p_u*p_uv)はちゃんとしてる
    • 嘘でした
  • これに加えてヒューリスティクスでちょっと収束速めている

アルゴリズム

  • SSSbyStep
    • ↑に書いた式で近似
  • GSbyStep
    • 線形系で近似
    • SSSの簡易版
    • 行列で表されるので、ガウスザイデルが出来る

ヒューリスティクス(MIP Heuristic)

  • 計算がうまくいかないというのは百も承知
    • 具体的に上手くいかない例が有る
  • 更新する回数を制限するとうまくいきそうという主張
    • その回数の決め方は謎

議論しないといけないこと

  • 収束するか?
  • 解が一意に定まるか?

実験

データセット

  • 400K辺が最大
    • 小さいなあ(´・ω・`)

比較対象

  • SSSbyStep
  • GSbyStep
  • GS
  • MIP
  • SSS
  • SP1M
  • GICM200
    • モンテカルロ200回

類似度

  • Monte-Carloで計算したtop-k個の頂点とどれくらい一致するか

σの値

  • なんかいい感じ何ですか?

計算時間

  • モンテカルロはどんどん遅くなる
  • 他はいっぺんに計算するから…

閾値の調査

  • 実験的にやってみましたよーって感じ?
  • 1がよかった

まとめ

  • どうなんですか…
  • IRIEと同様に議論が謎

PKDD influence maximization

2013-10-21 14:04:06 (Mon)

最終更新:2013年10月21日 14:04