Paper Info
Title
Communication-Free Massively Distributed Graph Generation
Abstract
Analyzing massive complex networks yields promising insights about our everyday lives. Building scalable algorithms to do so is a challenging task that requires a careful analysis and an extensive evaluation. However, engineering such algorithms is often hindered by the scarcity of publicly available datasets. Network generators serve as a tool to alleviate this problem by providing synthetic instances with controllable parameters. However, many network generators fail to provide instances on a massive scale due to their sequential nature or resource constraints. Additionally, truly scalable network generators are few and often limited in their realism. In this work, we present novel generators for a variety of network models commonly found in practice. By making use of pseudorandomization and divide-and-conquer schemes, our generators follow a communication-free paradigm. The resulting generators are often embarrassingly parallel and have a near optimal scaling behavior. This allows us to generate instances of up to 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">43</sup> vertices and 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">47</sup> edges in less than 22 minutes on 32768 cores. Therefore, our generators allow new graph families to be used on an unprecedented scale.
Year
DOI
Venue
2018
10.1109/IPDPS.2018.00043
2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Keywords
DocType
Volume
graph generation,communication-free,distributed algorithms
Conference
abs/1710.07565
ISSN
ISBN
Citations 
1530-2075
978-1-5386-4369-3
2
PageRank 
References 
Authors
0.37
22
6
Name
Order
Citations
PageRank
Daniel Funke151.16
sebastian lamm2344.10
Peter Sanders3225.45
Christian Schulz424024.10
Darren Strash523817.72
Moritz von Looz6304.11