Cost-effective Outbreak Detection in Networks

Cost-effective Outbreak Detection in Networks

  • Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance
  • KDD 2007

概要

  • outbreak detection問題を考える
  • 色々あるけど目的関数はsubmodularになるのが多い
  • 貪欲アルゴリズムで近似だ!
  • しかもsubmodularityを活かした高速化手法+online boundも考案
  • 安定のLeskovecといったところか

Outbreak detection

  • モチベーション: グラフ上でのカスケードを検知したい!
    • 水質汚染: 特定のノードにセンサを設置しておく
    • ブログの記事: 特定のブログをチェックして記事を(速く)キャッチ
  • イベントi
    • ノードs'から「何か」がカスケードする
    • パイプを通した汚染、記事の情報、等
  • センサーs∈A
    • sにたどり着くと検知…時刻T(i,s)
  • penalty π_i(t)
    • イベント毎に設定
  • 目的: minimize $$ \pi(A) \equiv \sum_{i}\Pr(i)\pi_i(T(i, A)) $$
    • $$ T(i,A) = \min_{s \in A}T(i,s) $$
  • 都合上 $$ R(A) = \pi(\emptyset) - \pi(A) $$の最大化にする
  • π_i(t)の例
    1. Detection likelihood: π_i(t)=0, π_i(∞)=1
    2. Detection time: π_i(t)=min{t, T_max}
    3. Population affected: π_i(t)=その時のカスケードサイズ, π_i(∞)=最終的なカスケードサイズ
  • 今述べたのについてR(A)はsubmodular!
  • でも?実際には目的関数はいろいろあるよね?
    • R(A) = (R_1(A), …, R_m(A))←このベクトルを小さくしたい
    • R(A) = Σ_i λ_iR_i(A) として最小化すると、「パレート最適」

提案手法

  • いつものごとく貪欲アルゴリズム
  • 問題: ノードにはコストc(s)がある(予算B以下)
  • いつものアルゴリズムを使うと、c(s)によって近似比保証が破綻する
  • かといって、gainをc(s)で割っても、worst caseでは矢張り破綻する
  • CEF(Cost-effective forward selection)
    • gainを"R(A_{k-1}∪{s})-R(A_{k-1})"と"[R(A_{k-1}∪{s})-R(A_{k-1})]/c(s)"にした場合で解を2つ計算して良い方を返す
    • 近似比は(1-1/e)/2
    • 実はO(B|V^4|)の1-1/eがあるけど、スケールしないし、↑で十分なのでやらない

高速化

  1. 関数評価
  • まぁ、割りとスパースだよね?
  • R_i({s})が0のところが結構ある
  • inverted indexでΣとるところを早くする
  • シナリオが沢山有るときには確かに効果的だな~

評価回数抑制

  • diminishing marginal returnを使った例のアレ
  • 遅延(lazy)評価

CASE STUDY 1: BLOG NETWORK

CASE STUDY 2: WATER NETWORKS

  • 色々しっかりと実験してなるほどこれは良いなあという感じ
  • 適当な時に読む

まとめ

  • 流れがさすがだなあと思った
  • それっておかしくね?みたいな所が少ない
  • 極限まで速い、ってわけではないけれど、シミュレーション依存なので、関数評価が少ないという点に重きをおいている
  • 結局submodularになるの結構あるけど、submodular以外に何かイイ性質無いかなあ…

KDD information diffusion sensor placement

2014-01-11 01:15:22 (Sat)

最終更新:2014年01月11日 01:15