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
-
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)の例
-
Detection likelihood: π_i(t)=0, π_i(∞)=1
-
Detection time: π_i(t)=min{t, T_max}
-
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があるけど、スケールしないし、↑で十分なのでやらない
高速化
-
関数評価
-
まぁ、割りとスパースだよね?
-
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