Properties of stochastic Kronecker graphs

DOI10.4310/JOC.2015.V6.N4.A1MaRDI QIDQ890578zbMATH OpenOpenAlexFDO

Authors Mihyun Kang, Michal Karonski, Christoph Koch, Tamás Makai

Publication date 10 November 2015

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6328

zbMATH Keywords

power lawrandom graphsdegree distributionsubgraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

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 $$ independently of the presence or absence of any other edge, for fixed parameters $$. 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 $$. In addition, we analyze the number of subgraphs present in the stochastic Kronecker graph and study the typical neighborhood of any given vertex.

Recommendations

• Stochastic Kronecker graphs
• Stochastic Kronecker Graphs
• The Kronecker theory of power law graphs
• Connectivity and giant component of stochastic Kronecker graphs
• Giant components in Kronecker graphs

Cited in

(8)

• The Kronecker theory of power law graphs
• An in-depth analysis of stochastic Kronecker graphs
• On matchings in stochastic Kronecker graphs
• Stochastic Kronecker Graphs
• Moment-Based Estimation of Stochastic Kronecker Graph Parameters
• Connectivity and giant component of stochastic Kronecker graphs
• Stochastic Kronecker graphs
• Giant components in Kronecker graphs

Describes a project that uses

Uses Software

• KronFit

This page was built for publication: Properties of stochastic Kronecker graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q890578)