3 years ago

Communication-free Massively Distributed Graph Generation.

Christian Schulz, Sebastian Lamm, Darren Strash, Peter Sanders, Daniel Funke, Moritz von Looz

Analyzing massive complex networks yields promising insights about our everyday lives. Building scalable algorithms to do that is a challenging task that requires a careful analysis and 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, i.e. they require no communication. The resulting generators are often embarrassingly parallel and have a near optimal scaling behavior. Overall, we are able to generate instances of up to $2^{43}$ vertices and $2^{47}$ edges in less than 22 minutes on 32768 processors. Therefore, our generators allow new graph families to be used on an unprecedented scale.

Publisher URL: http://arxiv.org/abs/1710.07565

DOI: arXiv:1710.07565v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.