「Assessing Attack Vulnerability in Networks with Uncertainty」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* Assessing Attack Vulnerability in Networks with Uncertainty
- Thang N. Dinh, My T. Thai
- INFOCOM 2015
* 概要
- ネットワーク脆弱性を「期待対連結性」で評価したい
- 「k頂点消すと期待対連結性はどれ位下がるか？」という離散最適化問題
- 提案手法は、LPによる緩和＋交換ヒューリスティクス
- 期待対連結性のFPRASを提案
* 期待対連結性
- 脆弱性の色々な尺度
-- 最短経路長、代数的連結性、連結成分数・サイズ…はあまり良くない
-- 対連結性 (pairwise connectivity)は結構良いらしい
- 致命的頂点検出問題 (critical node detection)
-- 普通のグラフで対連結性を最小化する問題
-- 近似手法いくつか
- 期待対連結性 (expected pairwise connectivity)
-- $$ \\textsf{EPC}(\mathcal{G}) = \frac{1}{2} \sum_{\{u,v\} \in {V \choose 2}} \textsf{rel}_{\mathcal{G}}(u,v) $$
* Assessing Attack Vulnerability in Networks with Uncertainty
- Thang N. Dinh, My T. Thai
- INFOCOM 2015
* 概要
- ネットワーク脆弱性を「期待対連結性」で評価したい
- 「k頂点消すと期待対連結性はどれ位下がるか？」という離散最適化問題
- 提案手法は、LPによる緩和＋交換ヒューリスティクス
- 期待対連結性のFPRASを提案
* 期待対連結性
- 脆弱性の色々な尺度
-- 最短経路長、代数的連結性、連結成分数・サイズ…はあまり良くない
-- 対連結性 (pairwise connectivity)は結構良いらしい
- 致命的頂点検出問題 (critical node detection; CND)
-- 普通のグラフで対連結性を最小化する問題
-- 近似手法いくつか
- 期待対連結性 (expected pairwise connectivity)
-- $$ \textsf{EPC}(\mathcal{G}) = \frac{1}{2} \sum_{\{u,v\} \in {V \choose 2}} \textsf{rel}_{\mathcal{G}}(u,v) $$
- 確率的致命的頂点検出問題 (probabilistic critical node detection; k-pCND)
-- k頂点取り除いてEPC(G)を最小化
* 提案手法
** 全体の流れ
- CNDはIPで記述できるらしい
- k-pCNDも確率的なIPとして考えられる
- MIP_F: 確率的な所を展開したIP
-- 変数・制約数が指数的になってショボンヌ
- MIP_R: 各ランダムグラフに関する制約を足し算でまとめる
-- MIP_Fの下限（最小化問題なので）にはなっている
+ MIP_Rを逐次的にk回解く
+ 交換ヒューリスティクスでEPCが下がるだけ更新する
** EPCの近似計算
- 相対誤差で多項式時間近似したい
+ $$ \sum_{e} (辺確率) < \frac{2}{1}\epsilon n^{-2} $$
-- $$ \sum_{e} (辺確率) $$で十分良い近似
-- ここをMonte-Carloすると大変
+ それ以外; 辺確率和がそこそこ大きい
-- 頂点uを一様無作為標本
-- uから（ランダムグラフ上の）BFSして連結成分サイズを計算
-- ごにょごにょする
* 実験
- すごーい！
- kの値が分からん…
* まとめ
- EPCの近似計算が少し面白いだけ
- これでINFOCOM的に評価されるんですかね…？
- 辺確率和が大きいときは、多分普通にやってもうまくいく
&tags()
2017/03/24
