  Large-scale analysis of the distributions of the network graphs observed in
naturally-occurring phenomena has revealed that the degrees of such graphs
follow a power-law or lognormal distribution. Seshadhri, Pinar, and Kolda (J.
ACM, 2013) proved that stochastic Kronecker graph (SKG) models cannot generate
graphs with degree distribution that follows a power-law or lognormal
distribution. As a result, variants of the SKG model have been proposed to
generate graphs which approximately follow degree distributions, without any
significant oscillations. However, all existing solutions either require
significant additional parameterization or have no provable guarantees on the
degree distribution.
  -- In this work, we present statistical and computational identifiability
notions which imply the separation of SKG models. Specifically, we prove that
SKG models in different identifiability classes can be separated by the
existence of isolated vertices and connected components in their corresponding
generated graphs. This could explain the large (i.e., $>50\%$) fraction of
isolated vertices in some popular graph generation benchmarks.
  -- We present and analyze an efficient algorithm that can get rid of
oscillations in the degree distribution by mixing seeds of relative prime
dimensions. For an initial $2\times 1$ and $2\times 2$ seed, a crucial
subroutine of this algorithm solves a degree-2 and degree-4 optimization
problem in the variables of the initial seed, respectively. We generalize this
approach to solving optimization problems for $m\times n$ seeds, for any $m,
n\in\mathbb{N}$.
  -- The use of $3\times 3$ seeds alone cannot get rid of significant
oscillations. We prove that such seeds result in degree distribution that is
bounded above by an exponential tail and thus cannot result in a power-law or
lognormal.
