COMPLEX NETWORK PARTITIONING USING LABEL PROPAGATION

doi:10.1137/15M1026183

2016-01-01

PRE

George M. Slota *

Kamesh Madduri

Sivasankaran Rajamanickam

DOI：10.1137/15M1026183

原文链接

原文求助

摘要

En 中文

We present PuLP (partitioning using label propagation), a parallel and memory efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions on shared-memory multicore platforms. Graph partitioning is an important problem in scientific computing because it impacts the execution time and energy efficiency of computations on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization. A novel feature of our PuLP method is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses up to 7.8x less memory than state-of-the-art partitioners and is 5.0x faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multiobjective scenario.

Keyword:

partitioning

label propagation

parallel

graph algorithm

small-world