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

Mihyun Kang (Institute of Optimization and Discrete Mathematics, Graz University of Technology, Graz, Austria)

Michał Karoński (Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland)

Christoph Koch (Institute of Optimization and Discrete Mathematics, Graz University of Technology, Graz, Austria)

Tamás Makai (Institute of Optimization and Discrete Mathematics, Graz University of Technology, Graz, Austria)

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

Full Text (PDF format)

Published 31 July 2015