Connectivity and giant component of stochastic Kronecker graphs

DOI10.4310/JOC.2015.V6.N4.A4zbMATH Open1325.05153arXiv1310.7652MaRDI QIDQ890583FDOQ890583

Authors: Mary Radcliffe, Stephen J. Young 

Publication date: 10 November 2015

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

Abstract: Stochastic Kronecker graphs are a model for complex networks where each edge is present independently according the Kronecker (tensor) product of a fixed matrix k-by-k matrix P with entries in [0,1]. We develop a novel correspondence between the adjacencies in a general stochastic Kronecker graph and the action of a fixed Markov chain. Using this correspondence we are able to generalize the arguments of Horn and Radcliffe on the emergence of the giant component from the case where k = 2 to arbitrary k. We are also able to use this correspondence to completely analyze the connectivity of a general stochastic Kronecker graph.

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

Recommendations

• Stochastic Kronecker graphs
• Stochastic Kronecker Graphs
• Giant components in Kronecker graphs
• Properties of stochastic Kronecker graphs
• On matchings in stochastic Kronecker graphs

zbMATH Keywords

Markov chaincomplex networks model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Connectivity (05C40)

Cited In (7)

• Title not available (Why is that?)
• Stochastic Kronecker Graphs
• On matchings in stochastic Kronecker graphs
• On the diameter of Kronecker graphs
• Properties of stochastic Kronecker graphs
• Stochastic Kronecker graphs
• Giant components in Kronecker graphs

This page was built for publication: Connectivity and giant component of stochastic Kronecker graphs

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