Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues (WWW'13)

主張

  • 無限グラフの固有値に比べて,切り取ってできた有限グラフの固有値はよくない
  • 境界を考慮して "Dirichlet 固有値" を使うことを提案

  • 有限の木と無限の木は,全然違う
  • 複雑ネットワークの構造
    • core-whisker
    • 各ペアに流量 1 のフローを流すと,O(n^2) の流量を処理する頂点が存在 (≒高 betweeness)

Dirichlet 固有値

  • 境界 ∂(S) : 適当に君たちが決めといてくれ
  • L_S: 境界を除いた内側に対応する部分行列
  • Dirichlet スペクトラルギャップ λ_S:L_S の最小非0固有値
    • グラフを変形してからつくるのではなく,行列にしてから抜く
    • なので,次数のあたりがおかしい.(もはや all 1 ベクトルは固有ベクトルとは限らない)
  • 局所コンダクタンス:局所版の Cheeger 不等式が成立!

実験してみる

  • インパクトある図 → こまごまと whisker を取り除くのではなく,ちゃんとグラフを綺麗に分割できた!
  • spectral clustering した時,生まれる連結成分数とかが減るので良い