Where Graph Topology Matters: The Robust Subgraph Problem - todo314 @ ウィキ

Where Graph Topology Matters: The Robust Subgraph Problem

• Hau Chan, Shuchu Han, Leman Akoglu
• SDM 2015

概要

• 輸送／通信ネットワークでは頑健性が大事
• 全体の頑健性でなく，局所的な頑健性に注目
  • どちらかというと部分グラフマイニング
• 密グラフっぽいけど目的関数がぜんぜん違う
  • 平均次数・辺密度は関係ない
• NP-hardなのでヒューリスティック2つ
• メモ
• どうやら全体的にMake It or Break It: Manipulating Robustness in Large Networksが大元のアイデアらしい

定義等

• 頑健性として，[Wu, Mauricio, Tan, Deng. 2010]のNatural connectivity（自然連結性）
• $$ \bar{\lambda}(G) = \log (\frac{1}{n} \sum_{1 \leq i \leq n}e^{\lambda_i}) $$
• λiは隣接行列の固有値（降順）
• Σのところは(#長さkの閉路)／k!の和と同じ
  • Estrada indexとか言われるらしい，タンパク質間ネットワークの何かと関連

• 平均次数と頑健性は違う
  • 関連があるけれど

問題定義

• 部分グラフなので，以下を|S|固定の下で最大化
• $$ \log \frac{\sum_{1 \leq i \leq |S|}e^{\lambda_i}}{|S|} $$
  • 平均固有値を最大化すればOK
• NP-hard
• 単調性やsemi-hereditary(?)は無い
• 変種
  1. サイズ制約無し
  2. top-k
  3. 特定の頂点集合を含む

提案手法

貪欲Top-down探索

• Vから頂点を1つずつ抜いていく
• 固有値の再計算は意外と簡単
  • Δ固有値をまず今の固有ベクトルとΔAから計算
  • Δ固有ベクトルを↑とかをもとに計算
• 固有ベクトル全部はきついので，上位幾つかだけ見る
  • 固有値が偏っているので

GRASP(Greedy Randomized Adaptive Search Procedure)

• 良さげな候補からランダムに選択

実験

• めんどいのであんま読んでない

まとめ

• 近似はできそう

SDM 密グラフ 頑健グラフ

2015/07/03 14:06