# Community detection in graphs - Chapter VII: Spectral Algorithms > 前: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] | 全体: [[Community detection in graphs]] ## 要約 本章は、グラフに付随する行列(遷移行列・ラプラシアン行列・右確率行列)の固有ベクトルを頂点の座標や類似度として用いる**スペクトル法**(spectral algorithms)群を概観する(p.41-42)。遷移行列 T の固有ベクトルは、グラフに明瞭なコミュニティ構造がある場合に特定のクラスタへ局在しうる。この局在の度合いを測る指標が参加比(participation ratio、式53)であり、局在した固有ベクトルが指すクラスタの実効サイズを示す(p.41)。隣接行列の固有ベクトルについても同様の局在が起こりうる(p.41)。 なお、章分割ファイル `ch-07.txt` の冒頭部分(印字ページ41上部)は、実際には前章 VI(モジュラリティの resolution limit に関する議論)の末尾であり、モジュラリティランドスケープを低次元可視化した図(FIG.16、代謝ネットワーク Treponema pallidum における準最適解の巨大な縮退を示す)を含む。本章の見出し「VII. SPECTRAL ALGORITHMS」自体はこれに続く箇所から始まる。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch07-fig16-modularity-landscape.png]] (FIG. 16. モジュラリティランドスケープの低次元可視化(代謝ネットワーク Treponema pallidum)。準最適解の巨大な縮退(プラトー)を示す。本図の議論自体は前章VI末尾の resolution limit に関するものであり、本章VIIの主題ではない (p.41)。) ## 分類軸(taxonomy) 本章のスペクトル法は、用いる行列とその活用方法によって以下のように分類できる。 - **遷移行列の固有ベクトルの局在** — 参加比によってクラスタの実効サイズを見積もる、Mitrović・Tadić によるモジュラーグラフのスペクトル性質の包括的解析、Slanina・Zhang による隣接行列固有ベクトルの局在化の議論 (p.41)。 - **ラプラシアン行列の固有ベクトルを座標とする埋め込み** — Donetti-Muñoz 法。M 個の固有ベクトル成分を頂点の座標として M 次元空間に埋め込み、階層的クラスタリングで分割する (p.41-42)。 - **ラプラシアン行列の固有値・固有ベクトルから導く物理量(実効コンダクタンス)** — Alves 法。グラフを電気回路とみなし類似度行列を構築する (p.42)。 - **右確率行列の固有ベクトルの相関** — Capocci et al. の手法。隣接行列を行和で正規化した右確率行列の固有ベクトル成分間のピアソン相関を類似度とする(議論は次章冒頭に続く) (p.42)。 ## 代表手法・システムの比較 **Donetti-Muñoz 法**は、ラプラシアン行列の M 個の固有ベクトルの成分を座標として各頂点を M 次元空間に埋め込む。コミュニティは互いに離れた点群として現れ、次元/固有ベクトル数 M が大きいほど分離が明瞭になる(p.41-42)。 > "Communities appear as groups of points well separated from each other, as illustrated in Fig. 17. The separation is the more visible, the larger the number of dimensions/eigenvectors M." (ch-07.txt:113-117) 分割には、辺で連結なクラスタ対のみを併合できる制約付き階層的クラスタリングを用い、得られたデンドログラムの断面のうちモジュラリティが最大のものを採用する(p.42)。M は事前には分からないため、M0 個までの固有ベクトルを計算し、1≤M≤M0 の範囲でモジュラリティ最大のものを探索する。頂点間の類似度には Euclidean 距離と角度距離(angle distance、原点から2点への角度に基づく)の双方が試され、Girvan-Newman ベンチマークでは complete-linkage クラスタリングが最良の結果を与える(p.42)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch07-fig17-spectral-algorithm-donetti.png]] (FIG. 17. Donetti-Muñoz のスペクトルアルゴリズム。ラプラシアン固有ベクトル成分を座標とした頂点埋め込みの例。1次元より2次元の方がコミュニティ分離が明瞭に現れる (p.41-42)。) 計算コストの中心はラプラシアン固有ベクトルの算出にあるが、Lanczos 法を用いれば少数の固有ベクトルのみを求めれば足りる場合が多い(p.42)。 > "The most computationally expensive part of the algorithm is the calculation of the Laplacian eigenvectors." (ch-07.txt:131-132) **Alves 法**は、ラプラシアンの固有値・固有ベクトルからグラフを電気回路とみなして各頂点対間の実効コンダクタンスを計算し、これを類似度行列として階層的クラスタリングを行う。ラプラシアンの全スペクトルを要するため計算量は O(n^3) であり、大規模グラフには不向きな低速な手法である(p.42)。 > "The algorithm by Alves is rather slow, as one needs to compute the whole spectrum of the Laplacian, which requires a time O(n3)." (ch-08.txt:6、冒頭は本章内容の続き) **Capocci et al. の手法**は、隣接行列を行和で正規化した右確率行列 R の固有ベクトル成分間のピアソン相関を頂点間類似度として用いる。右確率行列はラプラシアンと類似の性質を持つ。手法の詳細な説明はファイル境界を越えて次章冒頭に続く(p.42)。関連研究として、Simonsen による右確率行列の固有ベクトルで頂点を埋め込む手法も言及される(p.42)。 ## 傾向と未解決課題 - クリーンなクラスタ分離に必要な固有ベクトル数 M は事前には分からず、実務上は複数の M を試してモジュラリティで選ぶという探索的な対処に留まる(p.42)。 - Alves 法のデンドログラムから最良のパーティションを選ぶ明確な基準が示されていない(p.42)。 - スペクトル法全般の計算コストはラプラシアン(あるいは全スペクトルを要する手法ではラプラシアン全体)の固有ベクトル計算に集中する。Lanczos 法のような少数固有ベクトルの効率的な算出手段が実用上の鍵になる(p.42)。 - 本章の内容は原論文の章構成上、ファイル `ch-07.txt` の末尾で Capocci et al. の手法説明の途中(「eigenvalues are equal to 1, with eigenvectors character-」)に切れており、次章ファイル `ch-08.txt` の冒頭(Capocci et al. の議論の続き、FIG.18、Yang-Liu の recursive bisectioning)に続く。章分割ファイルの境界は原論文のセクション境界と厳密には一致しない。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[L. Donetti]] — ラプラシアン固有ベクトルに基づくスペクトルアルゴリズムの共同提案者(p.41-42)。 - [[M. A. Muñoz]] — 同上、共同提案者(p.41-42)。 - [[Alves]] — ラプラシアン固有値から実効コンダクタンスを計算する手法の提案者(p.42)。 - [[スペクトラルクラスタリング]] — 本章が扱う手法群の総称。 - [[コミュニティ検出]] — 本章はその一手法群(スペクトル法)を扱う。 - 前章: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]] — モジュラリティ最適化の各種手法、および本章冒頭に含まれる resolution limit の議論を扱う。 - 次章: [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] — Capocci et al. の手法の続き、および動的過程に基づくアルゴリズムを扱う。