  Stochastic Kronecker graphs are a model for complex networks where each edge
is present independently according the Kronecker (tensor) product of a fixed
matrix k-by-k matrix P with entries in [0,1]. We develop a novel correspondence
between the adjacencies in a general stochastic Kronecker graph and the action
of a fixed Markov chain. Using this correspondence we are able to generalize
the arguments of Horn and Radcliffe on the emergence of the giant component
from the case where k = 2 to arbitrary k. We are also able to use this
correspondence to completely analyze the connectivity of a general stochastic
Kronecker graph.
