Connectivity and giant component of stochastic Kronecker graphs

DOI10.4310/JOC.2015.V6.N4.A4MaRDI QIDQ890583zbMATHFDO

Authors Mary Radcliffe, Stephen J. Young

Publication date 10 November 2015

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

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

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)

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.

Recommendations

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

Cited in

(7)

• scientific article; zbMATH DE number 7560513 (Why is no real title available?)
• Stochastic Kronecker graphs
• Stochastic Kronecker Graphs
• On matchings in stochastic Kronecker graphs
• Properties of stochastic Kronecker graphs
• Giant components in Kronecker graphs
• On the diameter of 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)