Giant components in Kronecker graphs |
| |
Authors: | Paul Horn Mary Radcliffe |
| |
Affiliation: | 1. Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia;2. Department of Mathematics, University of California at San Diego, La Jolla, California |
| |
Abstract: | Let begin{align*}ninmathbb{N}end{align*}, 0 <α,β,γ< 1. Define the random Kronecker graph K(n,α,γ,β) to be the graph with vertex set begin{align*}mathbb{Z}_2^nend{align*}, where the probability that u is adjacent to v is given by pu,v =α u ? v γ( 1‐u )?( 1‐v )βn‐ u ? v ‐( 1‐u )?( 1‐v ). This model has been shown to obey several useful properties of real‐world networks. We establish the asymptotic size of the giant component in the random Kronecker graph.© 2011 Wiley Periodicals, Inc. Random Struct. Alg.,2011 |
| |
Keywords: | network Kronecker graph random graphs giant component |
|
|