「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と同様に議論が謎
&tags()
&update()