2013/10/29 by Mary Radcliffe, Radcliffe, Mary, Stephen J. Young +1
Computer Science · Mathematics · #05C80 #05C82 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Social and Information Networks (cs.SI) #cs.DM #cs.SI #math.CO #msc:05C80 #msc:05C82
paper · pdf · doi:10.48550/arxiv.1310.7652
14 pages
arxiv created 2015/04/01 · arxiv updated 2015/04/02
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.