|Title||Local graph sparsification for scalable clustering|
|Publication Type||Conference Paper|
|Year of Publication||2011|
|Authors||Venu Satuluri, Srinivasan Parthasarthy, Yiye Ruan|
|Conference Name||ACM SIGMOD International Conference on Management of data|
|Conference Location||Athens, Greece|
|Keywords||cation, Graph Clustering, Graph Sparsiﬁ, Minwise Hashing|
In this paper we look at how to sparsify a graph i.e. how to reduce the edgeset while keeping the nodes intact, so as to enable faster graph clustering without sacriﬁcing quality. The main idea behind our approach is to preferentially retain the edges that are likely to be part of the same cluster. We propose to rank edges using a simple similaritybased heuristic that we eﬃciently compute by comparing the minhash signatures of the nodes incident to the edge. For each node, we select the top few edges to be retained in the sparsiﬁed graph. Extensive empirical results on several real networks and using four state-of-the-art graph clustering and community discovery algorithms reveal that our proposed approach realizes excellent speedups (often in the range 10-50), with little or no deterioration in the quality of the resulting clusters. In fact, for at least two of the four clustering algorithms, our sparsiﬁcation consistently enables higher clustering accuracies.
|Full Text|| |
V. Satuluri, S. Parthasarathy, Y. Ruan. Local Graph Sparsification for Scalable Clustering. ACM SIGMOD International Conference on Management of data, 2011.