TY - GEN
T1 - Design, generation, and validation of extreme scale power-law graphs
AU - Kepner, Jeremy
AU - Samsi, Siddharth
AU - Arcand, William
AU - Bestor, David
AU - Bergeron, Bill
AU - Davis, Tim
AU - Gadepally, Vijay
AU - Houle, Michael
AU - Hubbell, Matthew
AU - Jananthan, Hayden
AU - Jones, Michael
AU - Klein, Anna
AU - Michaleas, Peter
AU - Pearce, Roger
AU - Milechin, Lauren
AU - Mullen, Julie
AU - Prout, Andrew
AU - Rosa, Antonio
AU - Sanders, Geoff
AU - Yee, Charles
AU - Reuther, Albert
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/8/3
Y1 - 2018/8/3
N2 - 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.
AB - 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.
KW - Extreme scale
KW - Graphs
KW - Kronecker
KW - Simulation
UR - http://www.scopus.com/inward/record.url?scp=85052222101&partnerID=8YFLogxK
U2 - 10.1109/IPDPSW.2018.00055
DO - 10.1109/IPDPSW.2018.00055
M3 - Conference contribution
AN - SCOPUS:85052222101
SN - 9781538655559
T3 - Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018
SP - 279
EP - 286
BT - Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 21 May 2018 through 25 May 2018
ER -