# Community detection in graphs - Chapter IV: Traditional methods > 前: [[@2010__PhysRep__Community detection in graphs - Chapter III Elements of Community Detection]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] | 全体: [[Community detection in graphs]] ## 要約 グラフ分割・階層的クラスタリング・分割型クラスタリング・スペクトラルクラスタリングという、コミュニティ検出以前から存在する4種の伝統的手法群を概観する章である。いずれもコミュニティ検出へ転用可能だが、クラスタ数の事前指定や選択基準の欠如といった構造的な限界を抱えている点が一貫して論じられる。 ## 分類軸(taxonomy) - **クラスタ数・サイズの既知/未知**: グラフ分割系(グラフ分割、分割型クラスタリング)はクラスタ数kを事前に与える必要があるのに対し、階層的クラスタリングは不要である。 - **最適化対象の測度**: 単純なカットサイズか、頂点数・次数で正規化した測度(conductance・ratio cut・normalized cut)か。 - **埋め込みの有無**: 分割型クラスタリングとスペクトラルクラスタリングはいずれも頂点をベクトル空間(距離空間、あるいはラプラシアン固有ベクトルによる空間)へ埋め込んでから分割する点で共通するが、後者はグラフ構造そのものから座標を導出する。 ## 代表手法・システムの比較 ### グラフ分割(graph partitioning) クラスタ数(場合によりサイズ)を事前に与えたうえで、クラスタ間のカットサイズを最小化する問題として定式化される。最小二分割(minimum bisection、等サイズ二分割でカット最小)はNP困難である。この事前指定の必要性こそが、クラスタ数もサイズも未知であることが多いコミュニティ検出への転用を本質的に妨げる(p.19)。 [[Kernighan and Lin]] は、頂点対のswapに基づく局所探索でカットサイズを最適化するKernighan-Linアルゴリズムを提案した。計算量はO(n^2 log n)で高速だが初期分割への依存が強く、単独での性能は振るわない。そのため他手法が出した分割を仕上げる後処理として使われることが多い(p.17-18)。 [[Fiedler]] はグラフラプラシアンの第2固有値(Fiedler値)に対応する固有ベクトル(Fiedlerベクトル)の符号を用いてグラフを二分割するスペクトラル二分法を提案した。厳密解ではないがカットサイズの良い近似解を与える(p.18)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch04-fig09-graph-partitioning.png]] (FIG. 9. 14頂点グラフにおける最小二分割問題の解の例。等サイズの2群へ最小カットで分割している。p.17) Ford and Fulkerson の max-flow min-cut定理(最大流と最小カットの等価性)はs-tカットの計算に利用され、Flake et al. はこれをWWWグラフへのコミュニティ検出に応用した(p.18-19)。 conductance・ratio cut・normalized cutは、いずれもカットサイズを頂点数または次数で正規化した測度群である。単純なカットサイズと異なり、これらの最適化は暗黙にクラスタサイズを均衡化する効果を持つが、最適化問題自体はやはりNP困難である(p.19)。 ### 階層的クラスタリング(hierarchical clustering) 頂点間の類似度に基づき、凝集型(agglomerative、下から結合)または分割型(divisive、上から分割)で樹形図(デンドログラム)を構築する。クラスタ間の類似度定義には単連結法・完全連結法・平均連結法(single/complete/average linkage)の3方式がある。クラスタ数・サイズの事前知識を要しない点が利点だが、生成される多数の分割候補のうちどれが「良い」分割かを選ぶ基準を持たず、樹形図自体が人為的な構造になりうるという弱点を抱える(p.19-20)。 ### 分割型クラスタリング(partitional clustering) 頂点を距離空間へ埋め込んだうえで、事前に指定したk個のクラスタへ分割する。MacQueenのk-meansクラスタリングが代表例で、Lloydのアルゴリズムで解かれることが多い。Bezdek・Dunnによるfuzzy k-meansは、1頂点が複数クラスタに多重所属することを許容する拡張である。いずれもクラスタ数kの事前指定を要し、結果は初期セントロイドに依存する局所最適解にとどまる(p.20-21)。 ### スペクトラルクラスタリング(spectral clustering) グラフラプラシアンの下位k個の固有ベクトルを用いて頂点をk次元空間に埋め込み、その空間上でk-means等により分割する手法である。最初期の提案はDonath and Hoffmannによる隣接行列の固有ベクトルを用いた版である(p.21)。 [[Shi and Malik]] はnormalized cutの最小化に基づき、ランダムウォークラプラシアンLrwを用いる正規化版を提案した。Ng et al.は正規化ラプラシアンLsymに基づく版を提案している。本節の解説はvon Luxburgのチュートリアルに依拠する(p.21-22)。非正規化/正規化ラプラシアン(L、Lrw、Lsym)は用いる行列が異なり、信頼性にも差がある。Meilă and Shiはnormalized cutとランダムウォークの遷移確率の等価性を証明した(p.22)。 ## 傾向と未解決課題 - 頂点次数の不均一が大きいグラフでは、非正規化ラプラシアンではなく正規化ラプラシアン(Lrw)を用いるべきである。正規化されたスペクトラルクラスタリング手法は、クラスタ内エッジ密度を高くしクラスタ間エッジ密度を低くするという二重最適化を暗黙に課すため、より有望とされる(p.22)。 - 疎グラフでは固有値ギャップ |λ_{k+1}-λ_k| の大きさが、Lanczos法の収束速度とクラスタ数推定の両方の手がかりになる(p.22)。 - グラフ分割・分割型クラスタリング系の手法をコミュニティ検出に流用する場合、クラスタ数を別途推定する仕組みと組み合わせる必要がある(p.19-20)。 - 未解決の問い: 元の最小カット問題(実際のグラフ分割上)と、その緩和版(スペクトラルクラスタリングによる連続緩和)との関係、すなわちスペクトラルクラスタリングが真の解にどれだけ近づけるかは、いまだ明らかではない(p.22)。 ## 関連 - ハブ: [[Community detection in graphs]] - entity: [[Kernighan and Lin]] / [[Fiedler]] / [[Shi and Malik]] - concept: [[スペクトラルクラスタリング]] - 前章: [[@2010__PhysRep__Community detection in graphs - Chapter III Elements of Community Detection]] - 次章: [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]]