Overlapping clusters for distributed computation

Reid Andersen, David F. Gleich, Vahab S. Mirrokni

Abstract

Most graph decomposition procedures seek to partition a graph into disjoint sets of vertices. Motivated by applications of clustering in distributed computation, we describe a graph decomposition algorithm for the paradigm where the partitions intersect. This algorithm covers the vertex set with a collection of overlapping clusters. Each vertex in the graph is well-contained within some cluster in the collection. We then describe a framework for distributed computation across a collection of overlapping clusters and describe how this framework can be used in various algorithms based on the graph diffusion process. In particular, we focus on two illustrative examples: (i) the simulation of a randomly walking particle and (ii) the solution of a linear system, e.g. PageRank. Our simulation results for these two cases show a significant reduction in swapping between clusters in a random walk, a significant decrease in communication volume during a linear system solve in a geometric mesh, and some ability to reduce the communication volume during a linear system solve in an information network.
BibTeX
@inproceedings{andersen2012overlapping,
  author = {Reid Andersen and David F. Gleich and Vahab S. Mirrokni},
  title = {{Overlapping clusters for distributed computation}},
  booktitle = {WSDM},
  year = {2012},
  doi = {10.1145/2124295.2124330},
}

Loading related content...

Figure