Scalable edge partitioning

DOI10.1137/1.9781611975499.17MaRDI QIDQ5232768zbMATH OpenOpenAlexFDO

Authors Sebastian Schlag, Christian Schulz, Daniel Seemaier, Darren Strash

Publication date 13 September 2019

Published in 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.06411

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Abstract: Edge-centric distributed computations have appeared as a recent technique to improve the shortcomings of think-like-a-vertex algorithms on large scale-free networks. In order to increase parallelism on this model, edge partitioning - partitioning edges into roughly equally sized blocks - has emerged as an alternative to traditional (node-based) graph partitioning. In this work, we give a distributed memory parallel algorithm to compute high-quality edge partitions in a scalable way. Our algorithm scales to networks with billions of edges, and runs efficiently on thousands of PEs. Our technique is based on a fast parallelization of split graph construction and a use of advanced node partitioning algorithms. Our extensive experiments show that our algorithm has high quality on large real-world networks and large hyperbolic random graphs, which have a power law degree distribution and are therefore specifically targeted by edge partitioning

Recommendations

• Graph partitioning for scalable distributed graph computations
• Distributed balanced partitioning via linear embedding
• Complex network partitioning using label propagation
• Algorithms for the Balanced Edge Partitioning Problem
• Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy

Cited in

(7)

• Distributed balanced partitioning via linear embedding
• Complex network partitioning using label propagation
• Parallelizing sequential graph computations
• Graph partitioning for scalable distributed graph computations
• Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy
• Theory and Applications of Models of Computation
• Buffered Streaming Graph Partitioning

This page was built for publication: Scalable edge partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232768)