  Graph analysis is playing an increasingly important role in science and
industry. Due to numerous limitations in sharing real-world graphs, models for
generating massive graphs are critical for developing better algorithms. In
this paper, we analyze the stochastic Kronecker graph model (SKG), which is the
foundation of the Graph500 supercomputer benchmark due to its favorable
properties and easy parallelization. Our goal is to provide a deeper
understanding of the parameters and properties of this model so that its
functionality as a benchmark is increased. We develop a rigorous mathematical
analysis that shows this model cannot generate a power-law distribution or even
a lognormal distribution. However, we formalize an enhanced version of the SKG
model that uses random noise for smoothing. We prove both in theory and in
practice that this enhancement leads to a lognormal distribution. Additionally,
we provide a precise analysis of isolated vertices, showing that the graphs
that are produced by SKG might be quite different than intended. For example,
between 50% and 75% of the vertices in the Graph500 benchmarks will be
isolated. Finally, we show that this model tends to produce extremely small
core numbers (compared to most social networks and other real graphs) for
common parameter choices.
