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 の最小非０固有値
  • グラフを変形してからつくるのではなく，行列にしてから抜く
  • なので，次数のあたりがおかしい．（もはや all 1 ベクトルは固有ベクトルとは限らない）
• 局所コンダクタンス：局所版の Cheeger 不等式が成立！

実験してみる

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