.png){kind=icon}
.png){kind=icon}
Return
COMPLEX NETWORK PARTITIONING USING LABEL PROPAGATION
.png){kind=icon}
PRE
AI
DOI：10.1137/15M1026183.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
partitioning
label propagation
parallel
graph algorithm
small-world
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W