Local Graph Sparsification for Scalable Clustering
-
Venu Satuluri, Srinivasan Parthasarathy, Yiye Ruan
-
SIGMOD 2011
概要だけ
-
クラスタリング手法 (Metis, Metis+MQI, MLR-MCL, Graclus) を疎化で高速化したい
-
基本アイデアは、「辺の重要度 = 近傍のJaccard類似度」
-
これだけだと、最密なコミュニティの辺の重要度が高すぎて、他のコミュニティ内の辺がなくなってしまう
-
各頂点の疎具合を制限するために、次数をd^eと設定
-
Jaccard類似度はMinHashで高速近似計算
-
比較実験で、速くなったし、クラスタリングのある種の質もあまり堕ちなかった
-
感想
-
これでSIGMODに通るんですねという印象
-
実験が凄く長いので、疎化したことによる効果を推している
SIGMOD クラスタリング 疎化
2016/12/28
最終更新:2016年12月28日 18:23