# Clique Percolation Method Palla et al. (Palla et al., 2005) が提案した、重複コミュニティ検出の代表的手法(Clique Percolation Method, CPM)。コミュニティ内部の辺は高密度なためクリークを形成しやすいという着想に基づき、大きさ k のクリーク(k-clique)同士が k-1 個の頂点を共有して連結する「k-clique chain」の連結成分(k-clique community)によってコミュニティを定義する。標準的な分割(partition)ではなく、頂点や辺が複数コミュニティに重複して属しうる cover を出力する([[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] p.58)。 > "The most popular technique is the Clique Percolation Method (CPM) by Palla et al. (Palla et al., 2005). It is based on the concept that the internal edges of a community are likely to form cliques due to their high density." (同 p.58) CPM はランダムグラフとコミュニティ構造を持つグラフを明確に区別できる利点を持つが、パーコレーション閾値 pc(k) を境に巨大な k-clique community の有無が急激に変化するというパーコレーション的性質を示す(同 p.58-59)。ソフトウェア実装として CFinder(Adamcsek et al., 2006)が配布されている(同 p.58-59)。 ## 拡張・派生 - Farkas et al. — 重み付きグラフ向けの k-クリーク重み閾値法。 - Lehmann et al. — 二部グラフ向け biclique コミュニティ検出への拡張。 - Kumpula et al. (2008) — 高速な逐次実装 Sequential Clique Percolation (SCP)。辺の重み降順に逐次挿入することで、全閾値の cover を一度に得られる。 (いずれも [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] p.59) ## 限界 - クリークが少ないグラフ(技術ネットワーク等)では意味のある cover を出せない。Radicchi et al. のアルゴリズム(Section V.B)と同じ限界を持つ。 - クリークが多すぎると、グラフ全体を1つのクラスタとする自明な分割になる。 - 次数1の頂点などクラスタに属せない頂点が残る。 - k の選び方に明確な基準がなく恣意的。 > "The CPM has the same limit as the algorithm of Radicchi et al. (Radicchi et al., 2004) (Section V.B): it assumes that the graph has a large number of cliques, so it may fail to give meaningful covers for graphs with just a few cliques" (同 p.59-60) (いずれも [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] p.59-60) ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] — 本手法を中心に扱う章。 - [[コミュニティ検出]] — 重複コミュニティ検出という下位分類に位置づけられる。 ## 出典 - [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] — Palla et al. (2005) による提案として言及される(原論文の書誌情報は本章の extract に含まれないため未記載)。