Sparsification of Influence Networks
-
Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, Antti Ukkonen
-
KDD 2011
概要
-
Yahoo! Research, Barcelonaの方々
-
尤度最大化という観点で辺をk本残す問題を提案
-
近似がNP-hard
-
最適解は頑張ってDPできる
-
貪欲アルゴリズムを提案(最適解に近い)
-
実験したら最強
-
influence maximizationにも使えるよ!
モデル
-
とりあえず,トレースから確率を推定したい
-
カスケードのトレースは頂点と時刻のペアの列とする
-
(v,t)についてvに影響する頂点の候補はいくつかあるけど分からない
-
F^+(v): vに影響する可能性があった
-
F^-(v): vに影響しない
-
特定のカスケードに対する尤度を
-
P^+(v) = F^+(v)の内のどれかがvに対して成功する確率
-
P^-(v) = F^-(v)のどれもvに対して成功しない確率
-
F(v)はFの入近傍
-
で定義する
-
これを各頂点,各カスケードについて掛け合わせる
-
確率を反復更新して尤度最大化(KES'08)
-
実際には離散時刻じゃないので,時間幅を設ける
問題
-
入力: グラフ,伝播確率,トレース,k
-
出力: サブグラフ
-
目標: サブグラフのトレースに対する尤度の最大化
-
難しさ
-
対数尤度が-∞になることがある
-
L(G_s)>-∞の解があるかの判定がNP-hard
-
だからmultiplicative factorの近似さえNP-hard
アルゴリズム
最適アルゴリズム
-
少しは早くなりそう
-
log L(G)はカスケードαと頂点vに関する和
-
頂点vに対する尤度だけ考える
-
Σ_α log P^+(v) + log P^-(v)
-
これは,vの親への辺(=D_v)を残すかどうかで決まる
-
D_vからb本選んで尤度最大化を個々に解く
-
で,k×nのDP
貪欲アルゴリズム: SPINE
-
ちょっと複雑
-
とりあえず適当な解=尤度が有限の解を求めている
-
その後から辺をイイ感じに選ぶ
-
何かしら(尤度の変形?)がsubmodularで1-1/e近似とか…
-
ところで,kの値はどうするのがいいの?
-
Bayesian Information Criterionの最小化
-
BIC(G_s) = -2log L(G_s) + k*log|A|
実験
-
確率でかい順とかランダムとかよりは圧倒的に尤度が高い
-
BICは有る所で最小値をとっている
-
実行時間は小さいデータでもかなりかかるなあ…
influence maximizationへの応用
-
そもそも↑の前処理として使うモチベーションだった
-
時間はかなり減っている,精度は落ちるが
まとめ
-
問題は面白いかな?
-
influence maximizationを高速化するなら確率を超小さくしてもいい気がしてきた…
-
でも,早くなるか分かりにくいか…
-
カスケードじゃない基準があればなあ
-
先行研究は無さそうだけど,関連は見といた方がいいかも
KDD influence maximization sparsification
2014-03-15 05:53:06 (Sat)
最終更新:2014年03月15日 05:53