Spectral Redemption: Clustering Sparse Networks

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