Minimizing the Spread of Contamination by Blocking Links in a Network - todo314 @ ウィキ

Minimizing the Spread of Contamination by Blocking Links in a Network

• Masahiro Kimura, Kazumi Saito, Hiroshi Motoda
• AAAI 2008

概要

• タイトルまんまの論文
• 汚染最小化問題
• 目的関数は各頂点のσの平均
• 既存の研究（Kempe依然）では，出次数の大きい順に頂点を消していけば大体良いとしてた
• 今回は辺を消す

問題定義

• min 1/|V|Σσ(v)
• Eからk辺取り除ける

提案手法

• 最も目的関数が小さい辺を選ぶ貪欲アルゴリズム
• σの計算がやばい
• この著者らが考えたBond Percolationで高速化

実験

• 比較手法
  • betweenness, out-degree, random
• out-degreeはだめぽ
  • 頂点じゃないので辺の次数をd(e=uv)=d(u)(v)

まとめ

• 理論的解析は全く無いんですね…
• 辺を消すって操作はかなり難しそう
• 既存がかなり古い，誰もやっていなかったのかな

AAAI contamination minimization

2014-02-17 03:57:31 (Mon)