# Peacock Gregory (2009) が提案した、重複コミュニティ検出のための前処理アルゴリズム。次の3段階からなる。 1. 各頂点の split betweenness(頂点分割によってどれだけ辺媒介中心性の再配分が生じるかを測る指標)に基づき、重複が疑われる頂点を複数の複製に分割し、重複のないグラフに変換する。 2. 変換後のグラフに標準的な(重複を仮定しない)クラスタリング手法を適用する。 3. 得られた分割を、分割された複製頂点を元の頂点に戻すことでマッピングし直し、重複コミュニティ構造を復元する。 計算量は厳密計算で O(n^3)、近似計算で O(n log n) である([[@2010__PhysRep__Community detection in graphs - Chapter XII Multiresolution methods and cluster hierarchy]] より、p.62)。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] — 重複コミュニティ検出手法の章。本手法の説明はこの章とChapter XIIにまたがる。 - [[@2010__PhysRep__Community detection in graphs - Chapter XII Multiresolution methods and cluster hierarchy]] — 本手法の複雑度を含む記述箇所。 ## 出典 - [[@2010__PhysRep__Community detection in graphs - Chapter XII Multiresolution methods and cluster hierarchy]] — Gregory (2009) による提案として言及される(原論文の書誌情報は本章の extract に含まれないため未記載)。