17. Overlapping communities in networks

  • Clique Percolation Method CPM
  • どのように k を選ぶか
    • "richest": サイズが最も幅広く分布するようにする
  • クリーク列挙法

How to Model Networks with Communities?

NCP
  • 頂点集合 S のクラスタらしさ:Conductance $\Phi(S)$
    • 小さい程よい
  • 定義 Network Community Profile (NCP)
    • 各 k に対し,サイズ k のコミュニティの最良値をプロットするグラフ

大規模な根とワークでは,NCP は,途中まで下がって,あるところから上がる\/

  • core-periphery structure
    • core をカバーすると周りと殆どつながっていない状態になって,とても良い

最良クラスタを削除しても,傾向が変わらない → どうやら core-periphery structure は入れ子構造のようだ!

従って提案される構造:Nested Core-Periphery (jellyfish, octopus)

Model

オーバーラップしない構造 (Ganovetter, Girvan-Newman),オーバーラップする構造 (CPM),どちらが正しいのか?

  • オーバーラップしないのはおかしい.
  • オーバーラップするにしても,オーバーラップしている部分は密でないという仮定(CPM)はおかしい.
  • オーバーラップしている部分はより密であるはずである.

Community-Affiliation Graph Model (AGM)