Make It or Break It: Manipulating Robustness in Large Networks
-
Hau Chan, Leman Akoglu, Hanghang Tong
-
SDM 2014
概要
-
グラフの頑健性の研究
-
色々な尺度
-
最大の連結成分の大きさ
-
逆最短経路長
-
代数的連結性 (algebraic connectivity)
-
理想は完全グラフ
応用
-
Power grid network
-
感染症ネットワーク
-
テロリストネットワーク
取り組むこと
-
頑健性の量化,グラフの操作
-
自然連結性(natural connectivity)
その他の頑健性との比較
-
最小頂点/辺カット
-
平均逆最短経路長
-
連結成分との距離(?)
-
代数的連結性
問題
-
僅かなグラフの変更で大幅に変化する
-
連結性や冗長な経路を捉えられない
-
効率的計算が難しい(?)
-
連結グラフでしか意味がない
-
非単調性がある
ネットワークの頑健性
-
$$ \bar{\lambda} = \ln (\frac{1}{n} \sum_{1 \leq j \leq n}e^{\lambda_j}) = \ln(\frac{1}{n}\mathrm{S}(G)) $$
-
S(G) := Estrada index, (#長さkの閉路)/k! の和
-
この閉路が代替経路と関連するので頑健性であることだなあ
問題定義
-
MIoBI (Mkae It or Break It)
-
MIoBI-BreakEdge (辺削除)
-
MIoBI-BreakNode (頂点削除)
-
MIoBI-MakeEdge (辺追加)
-
全探索はバカ
主な解き方
-
直接目的関数を最小化/最大化する辺/頂点を貪欲に選択する
-
固有対を全部持つのは無理,バカ
-
Top-tだけ持つ
-
BreakNode: O(kmt+knt^2)
-
MakeEdge: O(mt+kd^2t+knt^2)
-
kがデカイとつらそうに感じんだよなあ
実験
-
|V|<11K, |E|<40K
-
Top-t=50
-
毎回固有対を再計算するのは重いし,一辺足したくらいじゃそんなに変わらない
-
Naive: 毎回再計算
-
RC@50: 50操作毎に再計算
-
謎,勘違いかも
-
比較対象
-
無作為,次数,媒介中心性,有効抵抗,固有中心性,PageRank,等…
-
提案手法がほぼ最良
-
速度: mにほぼ線形している
まとめ
-
頑健っぽさを,実際の例,ワクチンとかではやらないのか…
-
後発の論文は部分グラフなので,↑のようなことをやっている?
-
多分遅い,のでこれだけでも頭良くできそう
-
あと,近似保証付きアルゴリズムが欲すぃ
SDM 密グラフ 頑健グラフ
2015/07/03 19:29
最終更新:2015年07月03日 19:31