  Random graph models are playing an increasingly important role in science and
industry, and finds their applications in a variety of fields ranging from
social and traffic networks, to recommendation systems and molecular genetics.
In this paper, we perform an in-depth analysis of the random Kronecker graph
model proposed in \cite{leskovec2010kronecker}, when the number of graph
vertices $N$ is large. Built upon recent advances in random matrix theory, we
show, in the dense regime, that the random Kronecker graph adjacency matrix
follows approximately a signal-plus-noise model, with a small-rank (of order at
most $\log N$) signal matrix that is linear in the graph parameters and a
random noise matrix having a quarter-circle-form singular value distribution.
This observation allows us to propose a ``denoise-and-solve'' meta algorithm to
approximately infer the graph parameters, with reduced computational complexity
and (asymptotic) performance guarantee. Numerical experiments of graph
inference and graph classification on both synthetic and realistic graphs are
provided to support the advantageous performance of the proposed approach.
