Distributed Graph Clustering and Sparsification

He Sun, Luca Zanetti

Research output: Contribution to journalArticlepeer-review

Abstract

Graph clustering is a fundamental computational problem with a number of applications in algorithm design, machine learning, data mining, and analysis of social networks. Over the past decades, researchers have proposed a number of algorithmic design methods for graph clustering. Most of these methods, however, are based on complicated spectral techniques or convex optimisation and cannot be directly applied for clustering many networks that occur in practice, whose information is often collected on different sites. Designing a simple and distributed clustering algorithm is of great interest and has comprehensive applications for processing big datasets.

In this article, we present a simple and distributed algorithm for graph clustering: For a wide class of graphs that are characterised by a strong cluster-structure, our algorithm finishes in a poly-logarithmic number of rounds and recovers a partition of the graph close to optimal. One of the main procedures behind our algorithm is a sampling scheme that, given a dense graph as input, produces a sparse subgraph that provably preserves the cluster-structure of the input. Compared with previous sparsification algorithms that require Laplacian solvers or involve combinatorial constructions, this procedure is easy to implement in a distributed setting and runs fast in practice.
Original languageEnglish
Article number17
Pages (from-to)1-23
Number of pages23
JournalACM Transactions on Parallel Computing
Volume6
Issue number3
Early online date2 Nov 2019
DOIs
Publication statusPublished - 1 Dec 2019

Keywords / Materials (for Non-textual outputs)

  • Graph clustering
  • graph sparsification
  • distributed computing

Fingerprint

Dive into the research topics of 'Distributed Graph Clustering and Sparsification'. Together they form a unique fingerprint.

Cite this