2014/10/23 by Mihyun Kang, Michał Karoński, Kang, Mihyun +5
Computer Science · Mathematics · Physics and Astronomy · #05C80 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis #math.CO #msc:05C80
paper · pdf · doi:10.48550/arxiv.1410.6328
37 pages, 2 figures
openalex publication_date 2014/10/23 · arxiv created 2015/02/03 · arxiv updated 2015/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The stochastic Kronecker graph model introduced by Leskovec et al. is a random graph with vertex set \mathbb Z2n, 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.