# Community detection in graphs - Chapter V: Divisive algorithms > 前: [[@2010__PhysRep__Community detection in graphs - Chapter IV Traditional methods]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]] | 全体: [[Community detection in graphs]] ## 要約 本章は、コミュニティ間の辺を辺中心性測度に基づいて逐次除去していく分割型(divisive)アルゴリズム群を扱う。分割型アルゴリズムは本質的に階層的クラスタリングの一種であり、類似度の低い頂点対の辺ではなくコミュニティ間辺を除去する点だけが伝統的手法と異なる(p.23)。中核をなすのは [[Girvan-Newman algorithm|Girvan-Newmanアルゴリズム]] であり、その基盤となる edge betweenness(辺媒介中心性)という尺度の導入から、複数の高速化版・変種、そして代替の中心性測度(edge clustering coefficient、information centrality)までを概観する。 ## 分類軸(taxonomy) 分割型アルゴリズムは、コミュニティ間の辺を識別する**中心性測度の選び方**によって分類できる。 **(1) edge betweenness に基づく方式** — Girvan-Newmanアルゴリズムとその高速化・変種群。edge betweenness は、全頂点対間の最短路がその辺を通過する頻度として定義される(p.23)。 > "Edge betweenness is the number of shortest paths between all vertex pairs that run along the edge." (p.23) この概念自体は Freeman が導入した site betweenness(1977)に起源を持ち、Anthonisse が Girvan-Newman法に先立って未公刊の技術報告で edge betweenness を導入していた(p.23)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch05-fig10-edge-betweenness.png]] (FIG. 10. コミュニティ間をつなぐ辺の edge betweenness が他の辺より顕著に高いことを示す模式図。) **(2) 局所的な代替測度** — edge clustering coefficient(Radicchi et al.)は、コミュニティ間辺がサイクルに乏しいという直感に基づく局所測度である。Watts and Strogatz の頂点 clustering coefficient 概念を辺に拡張したものであり、Girvan-Newmanより高速だがサイクルの少ないグラフでは橋渡し辺を識別できず性能が落ちる(p.25-26)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch05-fig11-edge-clustering-coefficient.png]] (FIG. 11. edge clustering coefficient の模式図。灰色2頂点間の辺について、可能な三角形5個のうち実在3個で係数3/5となる例。) **(3) 大域的な代替測度** — information centrality(Fortunato et al.)は、Latora and Marchiori のネットワーク効率(efficiency、全頂点対間の距離の逆数の平均)概念を用い、辺除去によるネットワーク効率の相対変化量を中心性とする。計算コストは Girvan-Newman より重い(p.26-27)。 ## 代表手法・システムの比較 [[Girvan-Newman algorithm|Girvan-Newmanアルゴリズム]] は、edge betweennessが最大の辺を逐次除去し、除去のたびに全辺のbetweennessを再計算する処理を繰り返す。生成される樹形図(dendrogram)のうち modularity が最大になる分割を選ぶ(p.23-24)。edge betweenness 版の計算量は疎グラフで O(n^3) であり、random-walk betweenness・current-flow betweenness(両者は等価)より高速で実用上良い結果を与えるが、n〜10000程度が実用上の上限とされる(p.24)。重み付きグラフへの拡張は edge betweenness を重みで割ることで対応できる(Newman, 2004)(p.24)。 高速化版としては、Tyler et al. がモンテカルロ的な中心点サンプリングで近似計算を行う方式を提案し、Wilkinson and Huberman がこれを遺伝子共起ネットワークやメール網へ適用した。Rattigan et al. は network structure index により計算量を O(m) まで落とす近似版を提案している(p.24-25)。Brandes による BFS ベースの betweenness 高速化手法も基盤技術として言及される(p.23-24)。 > "in the method of Tyler et al., edges are removed until all connected components of the partition are 'communities' in the sense explained above." (p.24) 変種としては、Chen and Yuan が non-redundant paths のみを数える改良版を、Holme et al. が頂点除去版(生化学ネットワークの階層構造解析に適用)を提案している。オーバーラップするコミュニティ構造への対応としては、Pinney and Westhead による頂点分割版と、Gregory による CONGA(Cluster Overlap Newman-Girvan Algorithm)がある(p.25)。 > "The algorithm of Girvan and Newman is unable to find overlapping communities, as each vertex is assigned to a single cluster." (p.25) edge clustering coefficient と edge betweenness の関係については、以下のような相関が指摘される。 > "edges with low edge clustering coefficient usually have high betweenness and vice versa, although the correlation is not perfect." (p.26) ## 傾向と未解決課題 - グラフが大規模(n≫10000)で Girvan-Newman 本来の計算量が重すぎる場合は、Tyler et al. や Rattigan et al. の近似高速化版が実務上の選択肢になる(p.24-25)。 - オーバーラップするコミュニティ構造を抽出したい場合は Pinney-Westhead 版や Gregory の CONGA が候補になる(p.25)。 - サイクルの少ないネットワーク(一部の社会的・非社会的ネットワーク)では edge clustering coefficient よりも edge betweenness に基づく手法の方が有効とされる(p.26)。 - 章内に明示的な "open problem" の宣言文は見当たらないが、edge clustering coefficient法がサイクルの乏しいグラフで橋渡し辺を識別できないという限界は、代替測度選択における実務上の判断基準として残る(p.26)。 - 本章末尾(V.B節 information centrality の計算量に関する議論)は次章([[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]])側と文が接続しており、information centrality の計算量(O(m^2n) 等)の議論は次章冒頭で完結する。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[Girvan-Newman algorithm|Girvan-Newmanアルゴリズム]] — 本章の中核をなす分割型アルゴリズム。edge betweenness最大辺の逐次除去とmodularityによる分割選択からなる(p.23-24)。 - [[モジュラリティ]] — Girvan-Newmanアルゴリズムが樹形図から最終分割を選ぶ基準として用いる。 - [[コミュニティ検出]] — 本章はその手法群の一系統(分割型)を扱う。 - 前章: [[@2010__PhysRep__Community detection in graphs - Chapter IV Traditional methods]] — 伝統的手法(グラフ分割、階層的クラスタリング)を扱う。 - 次章: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]] — modularityベースの手法群を扱う。