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不等式
木の固有値
複雑ネットワークの構造
-
入力が巨大グラフの一部の場合は、あんまり意味ないとこを切ろうとしてしまう
-
ホントはコアを切りたい
-
betweennessの高い頂点を分けるようなカットが欲しい
Dirichlet 固有値
-
頂点集合Sの境界∂(S)
-
Ls: S\∂(S)だけ残した部分行列
-
Dirichletスペクトルギャップ
-
コンダクタンスとかも同じ感じに定義できる
実験
Rocketfuelネットワーク
カット
-
見せ方がやべえ
-
Dirichletはつまんで引き出したみたい
固有値の比較
固有値によるグラフの切断
WWW spectral clustering
2013-10-17 23:35:32 (Thu)
最終更新:2013年10月17日 23:35