Contents Online

# Journal of Combinatorics

## Volume 6 (2015)

### Number 4

### Properties of stochastic Kronecker graphs

Pages: 395 – 432

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

#### Authors

#### Abstract

The stochastic Kronecker graph model introduced by Leskovec *et al.* is a random graph with vertex set $\mathbb{Z}^n_2$, 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 \lt \alpha, \beta, \gamma \lt 1$. Leskovec *et al.* 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 \lt \alpha, \beta, \gamma \lt 1$. In addition, we analyze the number of subgraphs present in the stochastic Kronecker graph and study the typical neighborhood of any given vertex.

#### Keywords

random graphs, power law, degree distribution, subgraph

#### 2010 Mathematics Subject Classification

05C80

Published 31 July 2015