Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues

Spectral Analysis of Communication Networks Using Dirichlet Eigenvalues

  • Alexander Tsiatas, Iraj Saniee, Onuttom Narayan, Matthew Andrews
  • In WWW 2013

概要

  • スペクトルグラフ理論
  • 有限グラフでは適切なカット・コミュニティが見つけられない
  • Dirichlet固有値を使うよ!

スペクトルグラフ理論

  • 正規化されたラプラシアン
    • degreeのところをちょっと変える
    • $$ 0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n \leq 2 $$
    • スペクトルギャップ$$ \lambda_2 $$
  • コンダクタンス
  • Cheeger不等式

木の固有値

  • d正則無限サイズ
  • d正則有限サイズ
    • 0に近づく

複雑ネットワークの構造

  • 入力が巨大グラフの一部の場合は、あんまり意味ないとこを切ろうとしてしまう
  • ホントはコアを切りたい
  • betweennessの高い頂点を分けるようなカットが欲しい
    • フローを止めたい

Dirichlet 固有値

  • 頂点集合Sの境界∂(S)
  • Ls: S\∂(S)だけ残した部分行列
    • もとのグラフの次数が保持されたまま
  • Dirichletスペクトルギャップ
    • Lsのスペクトルギャップ
  • コンダクタンスとかも同じ感じに定義できる
    • Cheeger不等式も成立する

実験

Rocketfuelネットワーク

  • インターネット全体の一部
    • 次数1の頂点の先もネットワークがある

カット

  • 見せ方がやべえ
  • Dirichletはつまんで引き出したみたい

固有値の比較

  • Dirichletは大きめ

固有値によるグラフの切断

  • 良いカット
    • コンダクタンスが小さい
    • 連結性分数が小さい

WWW spectral clustering

2013-10-17 23:35:32 (Thu)

最終更新:2013年10月17日 23:35