Overlapping Community Detection Using Seed Set Expansion - todo314 @ ウィキ

Overlapping Community Detection Using Seed Set Expansion

• Joyce Jiyoung Whang, David F. Gleich, Inderjit S. Dhillon
• CIKM 2013

概要

• コンダクタンスがいい感じになる重複コミュニティ検出手法を提案

提案手法

• 目標: 全体をカバーしつつ、最大のコンダクタンスを小さくしたい

1. Filtering
   • whiskerを取り除きたいので、以下のような分解をする
   • core=（ざっくりいうと）最大の2点連結成分
   • bridge=橋
   • whisker=残り
2. Seeding
   • 色々な手法でクラスタ中心を決める
   • Graclus centers, Spread Hubs, Local Optimal Egonets, Random Seeds
3. Seed Set Expansion
   • [Andersen-Chung-Lang. FOCS'06]で近似: εでコミュニティの大きさを調整
4. Propagation
   • whiskerを適当にくっつける

実験

• カバー-最大コンダクタンスのプロット図で、提案手法がナイスな事を主張
• ground truthがあるもので比較

まとめ

• 既存の知見＋理論的結果たちを組み合わせ、無難に上手くまとめた感じ
• こういうの＝[Andersen-Chung-Lang. FOCS'06]を分散とかそういうグラフ処理用途に使えんかな

CIKM コミュニティ検出

2016/12/27