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)