Propagation Time in Stochastic Communication Networks

Details Propagation Time in Stochastic Communication Networks Propagation Time in Stochastic Communication Networks

2006-08-22

arxiv.org/abs/math/0608561v1

Mathematics

Probability

Scientific paper

Dynamical processes taking place on networks have received much attention in recent years, especially on various models of random graphs (including small world and scale free networks). They model a variety of phenomena, including the spread of information on the Internet; the outbreak of epidemics in a spatially structured population; and communication between randomly dispersed processors in an ad hoc wireless network. Typically, research has concentrated on the existence and size of a large connected component (representing, say, the size of the epidemic) in a percolation model, or uses differential equations to study the dynamics using a mean-field approximation in an infinite graph. Here we investigate the time taken for information to propagate from a single source through a finite network, as a function of the number of nodes and the network topology. We assume that time is discrete, and that nodes attempt to transmit to their neighbors in parallel, with a given probability of success. We solve this problem exactly for several specific topologies, and use a large-deviation theorem to derive general asymptotic bounds, which apply to any family of networks where the diameter grows at least logarithmically in the number of nodes. We use these bounds, for example, to show that a scale-free network has propagation time logarithmic in the number of nodes, and inversely proportional to the transmission probability.

Affiliated with

Also associated with

No associations

Rating

Propagation Time in Stochastic Communication Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Propagation Time in Stochastic Communication Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Propagation Time in Stochastic Communication Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-110110