Overlapping Community Detection Using Seed Set Expansion
-
Joyce Jiyoung Whang, David F. Gleich, Inderjit S. Dhillon
-
CIKM 2013
概要
-
コンダクタンスがいい感じになる重複コミュニティ検出手法を提案
提案手法
-
目標: 全体をカバーしつつ、最大のコンダクタンスを小さくしたい
-
Filtering
-
whiskerを取り除きたいので、以下のような分解をする
-
core=(ざっくりいうと)最大の2点連結成分
-
bridge=橋
-
whisker=残り
-
Seeding
-
色々な手法でクラスタ中心を決める
-
Graclus centers, Spread Hubs, Local Optimal Egonets, Random Seeds
-
Seed Set Expansion
-
[Andersen-Chung-Lang. FOCS'06]で近似: εでコミュニティの大きさを調整
-
Propagation
実験
-
カバー-最大コンダクタンスのプロット図で、提案手法がナイスな事を主張
-
ground truthがあるもので比較
まとめ
-
既存の知見+理論的結果たちを組み合わせ、無難に上手くまとめた感じ
-
こういうの=[Andersen-Chung-Lang. FOCS'06]を分散とかそういうグラフ処理用途に使えんかな
CIKM コミュニティ検出
2016/12/27
最終更新:2016年12月27日 01:08