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)
-
計算がうまくいかないというのは百も承知
-
更新する回数を制限するとうまくいきそうという主張
議論しないといけないこと
実験
データセット
比較対象
-
SSSbyStep
-
GSbyStep
-
GS
-
MIP
-
SSS
-
SP1M
-
GICM200
類似度
-
Monte-Carloで計算したtop-k個の頂点とどれくらい一致するか
σの値
計算時間
-
モンテカルロはどんどん遅くなる
-
他はいっぺんに計算するから…
閾値の調査
-
実験的にやってみましたよーって感じ?
-
1がよかった
まとめ
PKDD influence maximization
2013-10-21 14:04:06 (Mon)
最終更新:2013年10月21日 14:04