Local graph sparsification for scalable clustering

TitleLocal graph sparsification for scalable clustering
Publication TypeConference Paper
Year of Publication2011
AuthorsVenu Satuluri, Srinivasan Parthasarthy, Yiye Ruan
Conference NameACM SIGMOD International Conference on Management of data
Pagination721-732
Conference LocationAthens, Greece
Keywordscation, Graph Clustering, Graph Sparsi&#64257, Minwise Hashing
Abstract

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 sacrificing 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 efficiently 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 sparsified 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 sparsification 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.
"project" : "SoCS"
"hasBookTitle" : "Proceedings of the 2011 ACM SIGMOD International Conference on Management of data"