Paper Info
Title
Design, Generation, and Validation of Extreme Scale Power-Law Graphs
Abstract
Massive power-law graphs drive many fields: metagenomics, brain mapping, Internet-of-things, cybersecurity, and sparse machine learning. The development of novel algorithms and systems to process these data requires the design, generation, and validation of enormous graphs with exactly known properties. Such graphs accelerate the proper testing of new algorithms and systems and are a prerequisite for success on real applications. Many random graph generators currently exist that require realizing a graph in order to know its exact properties: number of vertices, number of edges, degree distribution, and number of triangles. Designing graphs using these random graph generators is a time-consuming trial-and-error process. This paper presents a novel approach that uses Kronecker products to allow the exact computation of graph properties prior to graph generation. In addition, when a real graph is desired, it can be generated quickly in memory on a parallel computer with no-interprocessor communication. To test this approach, graphs with 1012 edges are generated on a 40,000+ core supercomputer in 1 second and exactly agree with those predicted by the theory. In addition, to demonstrate the extensibility of this approach, decetta-scale graphs with up to 10^30 edges are simulated in a few minutes on a laptop.
Year
DOI
Venue
2018
10.1109/IPDPSW.2018.00055
2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
Keywords
DocType
Volume
graphs,kronecker,simulation,extreme scale
Conference
abs/1803.01281
ISSN
ISBN
Citations 
2164-7062
978-1-5386-5556-6
2
PageRank 
References 
Authors
0.38
49
21
Name
Order
Citations
PageRank
Jeremy Kepner160661.58
Siddharth Samsi220124.09
William Arcand317517.77
David Bestor418119.08
Bill Bergeron516816.57
Tim Davis650.76
Vijay Gadepally744950.53
Michael Houle86310.42
Matthew Hubbell919220.93
Hayden Jananthan10144.78
Michael J. Jones1111341927.21
Anna Klein124910.10
Peter Michaleas1320120.93
Roger Pearce1424419.40
Lauren Milechin1510216.45
Julie Mullen1613815.22
Andrew Prout1718218.78
Antonio Rosa1817017.67
Geoffrey Sanders194410.66
Charles Yee2014715.14
Albert Reuther2133537.32