Sparsification of Influence Networks

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の入近傍
  • で定義する
  • これを各頂点,各カスケードについて掛け合わせる
    • 後でlogとるけどね
  • 確率を反復更新して尤度最大化(KES'08)
  • 実際には離散時刻じゃないので,時間幅を設ける

問題

  • 入力: グラフ,伝播確率,トレース,k
  • 出力: サブグラフ
  • 目標: サブグラフのトレースに対する尤度の最大化
  • 難しさ
    • 対数尤度が-∞になることがある
    • L(G_s)>-∞の解があるかの判定がNP-hard
      • Hitting Setとか…
    • だからmultiplicative factorの近似さえNP-hard

アルゴリズム

最適アルゴリズム

  • 少しは早くなりそう
  • log L(G)はカスケードαと頂点vに関する和
  • 頂点vに対する尤度だけ考える
    • Σ_α log P^+(v) + log P^-(v)
  • これは,vの親への辺(=D_v)を残すかどうかで決まる
  • D_vからb本選んで尤度最大化を個々に解く
    • 0≦b≦k
  • で,k×nのDP

貪欲アルゴリズム: SPINE

  • ちょっと複雑
  • とりあえず適当な解=尤度が有限の解を求めている
  • その後から辺をイイ感じに選ぶ
  • 何かしら(尤度の変形?)がsubmodularで1-1/e近似とか…
  • ところで,kの値はどうするのがいいの?
    • Bayesian Information Criterionの最小化
    • BIC(G_s) = -2log L(G_s) + k*log|A|

実験

  • 確率でかい順とかランダムとかよりは圧倒的に尤度が高い
  • BICは有る所で最小値をとっている
    • でも割合0.5ってでかくない?
  • 実行時間は小さいデータでもかなりかかるなあ…

influence maximizationへの応用

  • そもそも↑の前処理として使うモチベーションだった
  • 時間はかなり減っている,精度は落ちるが
    • どうでもいいけど,軸がわかりにくくてガチギレ

まとめ

  • 問題は面白いかな?
    • influence maximizationを高速化するなら確率を超小さくしてもいい気がしてきた…
    • でも,早くなるか分かりにくいか…
    • カスケードじゃない基準があればなあ
  • 先行研究は無さそうだけど,関連は見といた方がいいかも

KDD influence maximization sparsification

2014-03-15 05:53:06 (Sat)

最終更新:2014年03月15日 05:53