Spectral Redemption: Clustering Sparse Networks
-
Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, Pan Zhanga
-
PNAS 2010
概要
-
スペクトル法によるコミュニティ検出
-
固有値を使う
-
問題: グラフが疎だと検出できない
-
スペクトルが悲しい感じらしい
-
密…平均次数が(定数でも)割りと高い(10以上?)
-
主張: nonbacktracking行列なるものを使うとGOOD
-
Nonbacktracking 行列Bとは?
-
u→vいってv→uいってというのができない
-
B_ijのi,jが辺だとすればいい
-
最大固有値,第二固有値,その他の固有値について閉じた式 or boundがある
PNAS コミュニティ検出
2014/12/11
最終更新:2014年12月11日 17:45