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 $10^{12}$ 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.

arXiv comment8 pages, 6 figures, IEEE IPDPS 2018 Graph Algorithm Building Blocks (GABB) workshop

References in corpus (20)

• Emergence of scaling in random networks
• Spectrum of Controlling and Observing Complex Networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Mathematical Foundations of the GraphBLAS
• Percolation of localized attack on complex networks
• Static Graph Challenge: Subgraph Isomorphism
• Standards for Graph Algorithm Primitives
• pMatlab Parallel Matlab Library
• Streaming Graph Challenge: Stochastic Block Partition
• Graphs, Matrices, and the GraphBLAS: Seven Good Reasons
• Enabling Massive Deep Neural Networks with the GraphBLAS
• Using a Power Law Distribution to describe Big Data
• Design and Implementation of Knowledge Base for Runtime Management of Software Defined Hardware
• Novel Graph Processor Architecture, Prototype System, and Results
• PageRank Pipeline Benchmark: Proposal for a Holistic System Benchmark for Big-Data Platforms
• Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge
• Genetic Sequence Matching Using D4M Big Data Approaches
• Distributed Triangle Counting in the Graphulo Matrix Math Library
• Rapid Sequence Identification of Potential Pathogens Using Techniques from Sparse Linear Algebra
• Constructing Adjacency Arrays from Incidence Arrays

Cited by in corpus (3)

• GraphChallenge.org Triangle Counting Performance
• Optimizing Xeon Phi for Interactive Data Analysis
• On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices