Finding Maximal k-Edge-Connected Subgraphs from a Large Graph

Rui Zhou, Chengfei Liu, Jeffrey Xu Yu, weifa Liang, Baichen Chen, Jianxin Li, "Finding Maximal k-Edge-Connected Subgraphs from a Large Graph", EDBT'12.

EDBT 2012

maximal k-edge-connected な subgraph を多分全部抽出する？多分，maximal k-edge connected component は推移律的な感じで分割になるので，分割する．

コミュニティ検出等で quasi clique や k-core をよくやっているが，ああいうのは結構不自然なのをたまに含む（例は論文のすぐんとこに図が入ってる） ので，k-connected subgraph 抽出してみてはどうか，というので．たしかに！モチベーションはオモロイ！

  • 手法は，ベースとしては，stoer-wagnerで最小カットで分断することを繰り返す．でも遅すぎるので頑張る． (Sec.3)
  • Vertex Reduction (Sec. 4)
    • 頑張って適当な (maximal じゃないかもな) k-connected component さがして，それを事前に縮約！
  • Edge Reduction (Sec. 5)
    • よくわからん
  • Cut Optimization (Sec. 6)
    • 多分，最小カットじゃなくて k 以下のカットが見つかればそれでいい，みたいなのとかやってる

色々思うところあるなー

  • 実験結果
    • V=76K,E=509K -> K=25 で 1000 秒ぐらい，K=45 だと 10 秒ぐらい
      • 何個出てくるのか言え!!!!
    • Cut Optimization は凄い効いてる (1000 倍とか速くなってる)
    • 高々 10 倍ぐらいらしい

他のコミュニティ？検出手法ってどうなんだろう，調べたい

  • k-core decomposition は比べ物にならないほど凄い高速にもとまるのは知っております
    • ICDE'11 に on-disk でばく速にやる論文でてたとかそういうレベル
  • 他のは？？？？？？？
  • maximal clique 列挙はウノ先生！！（実装したことがあります）