Information spreading in a large population of active transmitters and passive receivers

Abstract

This paper discusses a simple stochastic model for the spread of messages in a large population with two types of individuals: transmitters and receivers. Transmitters, after receiving the message, start spreading copies of the message to their neighbors. Receivers may receive the message, but will never spread it further. We derive approximations of the broadcast time and the first passage times of selected individuals in populations of size tending to infinity. These approximations explain how much the fact that only a fraction of the individuals are transmitters slows down the propagation of information. Our results also sharply characterize the statistical dependence structure of first passage times using Gumbel and logistic distributions of extreme value statistics.

AMS subject classification: 60K35, 91D30, 92D25