Journal of Combinatorics

Volume 6 (2015)

Number 4

Connectivity and giant component of stochastic Kronecker graphs

Pages: 457 – 482

DOI: https://dx.doi.org/10.4310/JOC.2015.v6.n4.a4

Authors

Mary Radcliffe (Department of Mathematics, University of Washington, Seattle, Wash., U.S.A.)

Stephen J. Young (Department of Mathematics, University of Louisville, Kentucky, U.S.A.)

Abstract

Stochastic Kronecker graphs are a model for complex networks where each edge is present independently according to the Kronecker (tensor) product of a fixed matrix $P \in $[0, 1]$^{k \times k}$. 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.

Published 31 July 2015