Methods to Find Overlapping Communities
Community detection in graphs http://arxiv.org/abs/0906.0612
通常の手法は,1 頂点はちょうど 1 つのコミュニティに所属する.そうではなく,1 頂点が複数のコミュニティに所属し得るようなコミュニティ列挙の手法.
Clique Percolation (CPM)
- k-1 頂点を共有するクリークをくっつける事を繰り返すだけ
- 疎なら 10^5 頂点ぐらいでも実用的な速度が出るらしい(どのぐらいなんだ)
拡張
- 重み付きグラフ
- ある重み以上の辺のみを残す (標準的,一般的手法)
- クリークの重みを定義(辺重みの幾何的平均),それがある程度以上のものを残す
- threshold は,巨大な component ができるよりギリギリ大きくすると良い感じらしい
- 有向グラフ
- directed k-cliques
- bipartite clique
- bipartite cliques (bicliques)
高速なアルゴリズム
- Sequential Clique Percolation (SCP)
- 1 本ずつ辺を挿入し,新しく k-clique が作られたかをチェックする
- これは CPM より高速らしい(…?)
- 別の利点として,辺を入れる順番を重み降順にすれば,任意の重みの thresholding についての結果が一気に求まる
欠点
- ネットワークのクリーク
- technological network や一部の social network のような,クリークが少ない物では使えない
- 逆に,クリークだらけだと全部繋がってしまう
- 出てくるものは実際にはあまり dense とは限らない (e.g. クリークのチェーン)
- 次数の低い頂点が,全くコミュニティに所属しないことになってしまう
- k の値に任意性があり,どういう値を選べば良いのか
Other Techniques
評価関数系
その他
- spectral mapping, fuzzy clustering and optimization of a quality function のコンビネーション
- 頂点の類似性を用いた手法
- 枝の集合としてクラスタを定義する方法
- 頂点を分割した新しいグラフを作り,そこに通常のコミュニティ検出の手法を適用する方法 (Peacock)
追記
新しい情報を教えてもらった,感謝
@iwiwi 仕事速い… arxiv.org/abs/1205.0038 これSCPよりソーシャルグラフ向きで速いです クリーク間のintersectionを考えるのは最小木のみとしたりする工夫
— mosaさん (@mosa_siru) 1月 22, 2013