Local Graph Sparsification for Scalable Clustering - todo314 @ ウィキ

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