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 wide
applications for processing big datasets.
In this paper 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
components 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 component is easy to implement in a distributed way and
runs fast in practice.

本文提出了一个简单的分布式算法，基于采样方案将输入的密集图转化为稀疏的子图，并在多项式对数回合内完成图的聚类，同时具有高效的实现和处理大数据集的广泛应用。