Spreading of Messages in Random Graphs
Journal
Theory of Computing Systems
Journal Volume
48
Journal Issue
2
Pages
389-401
Date Issued
2011
Author(s)
Ching-Lueh Chang
Abstract
Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdo{double acute}s-Rényi random graph G(n,p). Whenever more than a ρε(0,1) fraction of a vertex v's neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n, p, δ ρ), needed to convince a δε{1/n,...,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n, p, δ ρ)= Ω(min{δ, ρ}n)with probability 1-n-Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρn) and (2) min-seed(n, p, δ, 1/2) = Ω(δn/ln(e/δ))with probability 1-exp (-Ω(δn))-n-Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p. © 2010 Springer Science+Business Media, LLC.
Type
journal article