Make It or Break It: Manipulating Robustness in Large Networks - todo314 @ ウィキ

Make It or Break It: Manipulating Robustness in Large Networks

• Hau Chan, Leman Akoglu, Hanghang Tong
• SDM 2014

• yamaguchiyutoさんのまとめ
• http://yamaguchiyuto.hatenablog.com/entry/2014/05/04/120705

概要

• グラフの頑健性の研究
  • 測定する
  • 追跡する
  • 操作する
  • 比較する
• 色々な尺度
  • 最大の連結成分の大きさ
  • 逆最短経路長
  • 代数的連結性 (algebraic connectivity)
• 理想は完全グラフ
  • O(n^2)は現実的に無理

応用

• Power grid network
  • リンクを足して頑健性増加
• 感染症ネットワーク
  • 重要な頂点を除いて頑健性を破壊
• テロリストネットワーク
  • 重要な通信路を遮断して極力頑健性を下げる

取り組むこと

• 頑健性の量化，グラフの操作
• 自然連結性(natural connectivity)

その他の頑健性との比較

• 最小頂点／辺カット
• 平均逆最短経路長
• 連結成分との距離(?)
• 代数的連結性
  • 第二最小固有値に関連

問題

1. 僅かなグラフの変更で大幅に変化する
2. 連結性や冗長な経路を捉えられない
3. 効率的計算が難しい(?)
4. 連結グラフでしか意味がない
5. 非単調性がある

• こういうのは辛い

ネットワークの頑健性

• $$ \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 (辺削除)
  • 頑健性が最も減少するk辺
• MIoBI-BreakNode (頂点削除)
  • 頑健性が最も減少するk頂点
• MIoBI-MakeEdge (辺追加)
  • 頑健性が最も増加するk辺（まだグラフに無い）
• 全探索はバカ

主な解き方

• 直接目的関数を最小化／最大化する辺／頂点を貪欲に選択する
• 固有対を全部持つのは無理，バカ
• 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，等…
• 提案手法がほぼ最良
  • NaiveはRC@50よりしょぼい
• 速度: mにほぼ線形している
  • kについても線形

まとめ

• 頑健っぽさを，実際の例，ワクチンとかではやらないのか…
  • 後発の論文は部分グラフなので，↑のようなことをやっている？
• 多分遅い，のでこれだけでも頭良くできそう
• あと，近似保証付きアルゴリズムが欲すぃ

SDM 密グラフ 頑健グラフ

2015/07/03 19:29