Properties of stochastic Kronecker graphs

Original · EN

The stochastic Kronecker graph model introduced by Leskovec et al. is a random graph with vertex set Z₂ⁿ, where two vertices u and v are connected with probability αu·vγ(1-u)·(1-v)βn-u·v-(1-u)·(1-v) independently of the presence or absence of any other edge, for fixed parameters 0<α,β,γ<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<α,β,γ<1. In addition, we analyze the number of subgraphs present in the stochastic Kronecker graph and study the typical neighborhood of any given vertex.