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

評価関数系
  • Iterative Scan (IS)
    • 適当なシード頂点集合から,貪欲に評価関数が上がるように頂点を加えたり削除したりする
  • Rank Removal (RaRe)
    • 重要な頂点(これは適当な中心性を用いる)を削除していき,複数のコンポーネントに分ける
    • これらを,クラスターのコアとみなす
    • クラスターについて,削除した頂点のうちくっつけたら評価関数が上がるものを入れる
  • RaRe したあとで IS で結果を良くするというのが良いらしい
    • この組合せをもう少し頑張った論文も存在
その他
  • spectral mapping, fuzzy clustering and optimization of a quality function のコンビネーション
  • 頂点の類似性を用いた手法
  • 枝の集合としてクラスタを定義する方法
  • 頂点を分割した新しいグラフを作り,そこに通常のコミュニティ検出の手法を適用する方法 (Peacock)

追記

新しい情報を教えてもらった,感謝