# コミュニティ検出 ## 定義 ネットワークを、密に接続したノード集合(コミュニティ)へ分割するタスク。同一コミュニティ内のノードは密に、異なるコミュニティ間のノードは疎に接続することを目指す。分割アルゴリズムは大きく、コミュニティ間リンクを除去する分割法(divisive)、類似ノード/コミュニティを再帰的に統合する凝集法(agglomerative)、目的関数(多くはモジュラリティ)を最大化する最適化法に分類される([[@2008__JSTAT__Fast unfolding of communities in large networks]])。 ## 子概念 - [[モジュラリティ]] — コミュニティ分割の品質を測る目的関数。 - [[Louvain法]] — モジュラリティ最適化を高速化する代表的な階層的手法。 ## 未解決の問い - 大規模ネットワークにおいて、計算時間ではなくストレージ容量が律速となる場面でのアルゴリズム設計はどうあるべきか([[@2008__JSTAT__Fast unfolding of communities in large networks]] の考察)。 - Leskovec et al. の core-periphery 的知見は、conductance という指標固有の性質による人為的な産物(artefact)ではないか。他の指標・手法での検証が必要(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XVI General properties of real clusters]])。 - 頂点クラスタリングと辺クラスタリングのどちらが重複コミュニティ検出として本質的に優れているかは自明でなく、両者は対称的な問題を抱える(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]]) - 動的コミュニティ検出において、スナップショット間でコミュニティを対応付ける一般的な処方箋(最大重複基準が失敗する場合を避ける方法)は存在するか(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XIII Detection of dynamic communities]]) - クラスタリングアルゴリズムが満たすべき条件を定める理論的枠組みが不在であり、コミュニティの定義に研究者間の合意がないため手法の優劣を客観的に決められない(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]]) - コミュニティ・分割の基礎概念について分野内合意を伴う信頼できるベンチマーク群が未整備である。LFR ベンチマーク(Lancichinetti–Fortunato, 2009)や Sawardecker et al. (2009) が前進とされるが決定打はまだ無い(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]]) - 実グラフの多くは階層構造を持ち複数の意味のある分割が並立するため、単一の最良分割という発想自体が問題含みであり、階層的分割の情報をどう扱うべきかが未解決(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]]) - 構造情報と非構造情報(頂点属性等)を整合的に統合してクラスタリングする手法が未確立(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]]) - 有向・重み付き・二部・符号付きグラフへの手法拡張は予備的な試みの段階に留まり改善の余地が大きい(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]]) ## 未編纂の観察 [Louvain法] 従来最速だったCNM法([[@2008__JSTAT__Fast unfolding of communities in large networks]] 内で言及、Clauset・Newman・Moore 2004)は、超巨大コミュニティを生成する傾向があり100万ノード超のネットワークに事実上適用できなかった。Wakita & Tsurumi 法はコミュニティサイズのバランス化トリックで数百万ノード規模まで対応したが、バランス化ヒューリスティックのため低いモジュラリティしか得られない場合がある(Source: [[@2008__JSTAT__Fast unfolding of communities in large networks]])。 - [スペクトル法] グラフに付随する行列(遷移行列・ラプラシアン・右確率行列)の固有ベクトルを頂点の座標や類似度として用いるスペクトラルクラスタリングも、モジュラリティ最適化やLouvain法と並ぶ手法系統の一つである。Donetti-Muñoz法はラプラシアン固有ベクトルを座標に頂点を埋め込み階層的クラスタリングで分割する(Source: [[@2010__PhysRep__Community detection in graphs - Chapter VII Spectral Algorithms]]) - [実クラスタの一般的性質] 用いる検出アルゴリズムに依存せず、実データのコミュニティサイズ分布はしばしばベキ乗則(指数1〜3程度)に従い特徴的サイズを持たない。Leskovec et al. (2008) は多数の実ネットワークについて network community profile plot(部分グラフサイズ vs 最小 conductance)を計算し、~100頂点規模までは conductance が下がりそれ以降は単調に上昇するという共通形状を発見した。これは「良い」コミュニティが小規模なものに限られ、大規模な塊は周辺的な小クラスタ(whisker)が疎に接続した中心コアとみなせるという core-periphery 描像を示唆する(Source: [[@2010__PhysRep__Community detection in graphs - Chapter XVI General properties of real clusters]])。 - [重複コミュニティ検出] 標準的な分割(partition)ではなく、頂点や辺が複数コミュニティに同時に属しうる cover を出力する手法系統が別に存在する。代表は k-クリークの連結成分でコミュニティを定義する [[Clique Percolation Method]] (CPM, Palla et al.) で、重み付き・二部グラフへの拡張や高速化実装 (SCP) を持つが、クリークが少ないグラフには適用できず k の選択も恣意的という限界がある。頂点でなく辺をクラスタリング単位とする line graph 分割や hierarchical link clustering も代替アプローチとして提案されている(Source: [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]]) - [有意性評価] グラフ全体が modular でない可能性がある場合、パーティション全体ではなく個々のコミュニティ単位で有意性を問う指標が有用である。Lancichinetti et al. の C-score は、同じ次数列を持つランダムグラフの部分グラフである確率として定義され(最も内部次数の低い「worst」頂点の統計に基づく)、C-score ≤ 5% であればランダムな揺らぎの産物ではなく真のコミュニティである強い根拠となる。ただしnull modelがNewman-Girvanと同一で非現実的という弱点があり、頂点ごとの「horizon」概念に基づくより現実的なnull modelの定義は未解決である(Source: [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]])。 - [動的コミュニティ検出] 時間発展するグラフのコミュニティ検出は、各時刻を独立にクラスタリングしてから対応付ける二段階アプローチと、現在の構造への適合(snapshot quality)と過去の分割との整合性(history cost)を同時に最適化する evolutionary clustering の2系統に大別される。前者はノイズに弱く分割の見かけ上の変動がアーティファクトになりやすい(Source: [[@2010__PhysRep__Community detection in graphs - Chapter XIII Detection of dynamic communities]]) ## 関連 - 概念: [[スペクトラルクラスタリング]] - ソース: [[@2010__PhysRep__Community detection in graphs - Chapter XVI General properties of real clusters]] / [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] / [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]] / [[@2010__PhysRep__Community detection in graphs - Chapter XIII Detection of dynamic communities]] / [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]] - エンティティ: [[Clique Percolation Method]] / [[GraphScope]] / [[FacetNet]]