Properties of stochastic Kronecker graphs

Abstract

The stochastic Kronecker graph model introduced by Leskovec et al. is a random graph with vertex set ${\mathbb{Z}}_2^n$, where two vertices $u$ and $v$ are connected with probability ${\alpha }^{u\cdot v}{\gamma }^{(1-u)\cdot (1-v)}{\beta }^{n-u\cdot v-(1-u)\cdot (1-v)}$ independently of the presence or absence of any other edge, for fixed parameters $0<\alpha ,\beta ,\gamma <1$. They have shown empirically that the degree sequence resembles a power law degree distribution. In this paper we show that the stochastic Kronecker graph a.a.s. does not feature a power law degree distribution for any parameters $0<\alpha ,\beta ,\gamma <1$. In addition, we analyze the number of subgraphs present in the stochastic Kronecker graph and study the typical neighborhood of any given vertex.

37 pages, 2 figures