> 前: [[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] | 全体: [[Community detection in graphs]] # Community detection in graphs - Chapter X: Alternative methods ## 要約 前章までのモジュラリティ・スペクトル法・統計的推論などの主要カテゴリに収まらない、多様なコミュニティ検出手法を紹介する章。ラベル伝播、局所法(L-shell、局所モジュラリティ)、物理アナロジー(抵抗ネットワーク)、幾何学的視点(クラスタリング係数、動的シンプレックス埋め込み)、グラフ近似の定式化など、系統だった分類の外側にある手法群を並置している。 ## 分類軸(taxonomy) 本章の手法は明確な単一分類軸を持たず、次のような性質で緩やかにグループ化できる。 - **反復ラベル更新型**: ラベル伝播とその改良版(制約付き最適化、スコア減衰)。 - **局所拡張型**: 始点頂点から境界指標(emerging degree、局所モジュラリティ)を用いて逐次拡張する手法。 - **物理・幾何アナロジー型**: 抵抗ネットワーク、クラスタリング係数による曲率解釈、動的シンプレックス進化。 - **グラフ近似・間接検出型**: CLGA によるグラフ近似の最適化定式化、補グラフにおける反コミュニティ探索。 ## 代表手法・システムの比較 ### ラベル伝播(label propagation) Raghavan らの手法は、各頂点に一意なラベルを与えたのち、収束するまで近傍の多数派ラベルを採用する反復のみで分割を得る。1 反復あたり計算量 O(m) と非常に高速で、クラスタ数もサイズも事前指定不要である。 > "Vertices are initially given unique labels...each vertex takes the label shared by the majority of its neighbors." ただし解が一意でなく、複数分割を集約することで重複コミュニティを検出できる一方、集約するほど分割が細分化されるという欠点がある。Barber-Clark は制約付き目的関数でこれを改善し、Leung らはラベルに伝播距離で減衰するスコアを導入して、元の手法が SNS で「一つの巨大コミュニティ+多数の小コミュニティ」を生む病理を修正した。Tibély-Kertész は、ラベル伝播が零温度 Potts モデルの局所エネルギー極小探索と等価であることを示し、理論的裏付けを与えている。 ### 局所法(L-shell、Bridge Bounding、局所モジュラリティ) Bagrow-Bollt の L-shell 法は、始点頂点から測地距離の殻(shell)を順に追加し、内外の辺比(emerging degree)が閾値を超える限り拡張する。高速だが、始点がコミュニティ境界からほぼ等距離でないとうまく機能しない。 > "the L-shell method is very fast and can identify communities very quickly. Unfortunately the method works well only when the source vertex is approximately equidistant from the boundary of its community." da Fontoura Costa のハブ中心の殻拡張法が先行アイデアであり、Rodrigues らは境界頂点を別扱いする変種を、Papadopoulos らは Bridge Bounding 法を提案している。 Clauset の局所モジュラリティ R は、コミュニティ C の境界の鋭さを測る比率であり、貪欲最適化により局所探索的にコミュニティを検出する。 > "The local modularity R by Clauset is the ratio of the number of edges having both endpoints in C (but at least one in B), with the number of edges having at least one endpoint in B." ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch10-fig22-local-modularity.png]] (FIG. 22. Clauset の局所モジュラリティにおけるコミュニティ C とその境界 B の模式図。) 計算量は O(n_c^2 ⟨k⟩)(n_c はコミュニティサイズ)で、事前にコミュニティサイズを決めておく必要がある。Hui らは移動体通信網解析にこの手法を応用した。 ### 物理アナロジー・幾何学的視点 Eckmann-Moses はクラスタリング係数を用い、頂点近傍間の平均距離の「曲率」的解釈からコミュニティをグラフの高曲率領域として捉える幾何学的視点を提示し、WWW への適用例を示した。 Wu-Huberman はグラフを抵抗ネットワーク(resistor network)として扱い、電位差から 2 分割を O(n log n) で高速に検出する。任意頂点の所属コミュニティのみを求めることも可能である。Flake らの max-flow を用いた類似の局所法(第 IV 章参照)、Orponen-Schaeffer の拡散に基づく類似手法(始点未指定でも動作)、Ohkubo-Tanaka のコミュニティの「体積」最小化基準も同系統に位置づけられる。 Gudkov-Montealegre は動的シンプレックス(simplex)進化による幾何学的埋め込みで、コミュニティを空間クラスタとして検出する手法を提案した。 ### グラフ近似・間接検出 Long らの CLGA(Community Learning by Graph Approximation)は、元のグラフをコミュニティ構造を持つ「原型グラフ」に近似する最適化問題として定式化し、伝統的なグラフ分割を特殊ケースとして含む。 Zarei-Samani は補グラフ(complement graph)における反コミュニティ(anti-community, 多部構造)探索によってコミュニティを間接的に検出するスペクトル法を提案しているが、疎グラフの補グラフは密になるため、大規模グラフへの適用には限界がある。 ## 傾向と未解決課題 - ラベル伝播は大規模ネットワークの高速解析に向くが、複数回実行して分割を集約する運用は細分化を招くため注意が必要であり、Barber-Clark の制約付き最適化や Leung らのスコア減衰による緩和策があるものの、大規模グラフでの挙動は依然投資すべき問題として残る。 - L-shell 法や Bridge Bounding は局所的にコミュニティを高速に見つけられるが、境界を判定する閾値の選び方に明確な基準がなく、経験的に決める必要がある。 - Zarei-Samani の反コミュニティ法は小規模グラフでのみ検証されており、疎グラフの補グラフが密になる問題への対処は示されていないため、大規模疎グラフには不向きである。 - 章末は Krawczyk-Kulakowski による微分方程式ベースの手法への言及で途切れており、内容は次章(第 XI 章)側に続く。 ## 関連 - ハブ: [[Community detection in graphs]] - 概念: [[モジュラリティ]](Clauset の局所モジュラリティ R は本章固有の局所版バリアント) - 前章: [[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] - 次章: [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]]