  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.
