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

[Ognir]

http://arxiv.org/pdf/1412.7563.pdf


23 Dec 2014
Information spreading in a large population of
active transmitters and passive receivers
Pekka Aalto Lasse Leskel

December 25, 2014
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  lows 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.

Keywords
: rumor spreading, randomized broadcasting, first-passage
percolation, stochastic epidemic model
1 Introduction
Background and objectives.
Analyzing the spread of information in computer and social networks has become important as more and more communication takes place over highspeed digital connections. Especially, messages in online social networks tend to spread extremely fast due to the ease of copying and relaying messages. A simple mathematical model for the spreading phenomenon is to assume that individuals relay copies of messages at random time instants to randomly chosen neighbors In a graph that represents the communication infrastructure. In contexts where individuals keep on transmitting a message for a long time, a key quantity is the broadcast time, the time it takes to spread a message from a single root node to
∗
Department of Mathematics and Statistics, PO Box 35, 40014 University of Jyv ̈askyl ̈a, Finland. Email: aalto.pekka@gmail.com

Department of Mathematics and Systems Analysis, PO Box 1110
0 0076 Aalto Uni-
versity, Finland. URL: Email:
lasse.leskela@aalto.fi
1
all individuals connected to the root, and the
first passage time
, the time it
takes for a message to propagate from the root to a selected ta
rget. Such
models have been studied under different names in various area
s, such as ma-
terials science (first-passage percolation), computer net
works (randomized
broadcasting), and epidemiology (SI model, SIR model).
A special feature of online social networks is that different i
ndividuals
tend to behave in a highly different manner, with some individu
als quickly
relaying most messages they receive, and some hardly ever re
laying any-
thing. Analyzing the effect of such heterogeneity calls for st
ochastic spread-
ing models in random environments, for which the literature
appears scarce.
As a step towards more comprehensive analysis of random broa
dcasting in
random environments, we study a simple communication model
on a ho-
mogeneously mixing population which can be divided into tra
nsmitters and
receivers of a selected message. The
transmitters
(or spreaders) will start
relaying copies of the message to their neighbors after rece
iving it, whereas
the
receivers
(or stiflers) never relay the message. Our focus will be on
an asynchronous communication mode where individuals make
contacts to
randomly chosen neighbors at random time instants, indepen
dently of each
other. When a contact is made, a copy of the message is sent fro
m the source
to the target if the source was an informed transmitter of the
message. Our
main research question is:
How much does the fact that only a small fraction of the indi-
viduals relay the selected message slow down the spread of in
for-
mation?
Related work: Homogeneous populations.
In a large homogeneous
population of size
n
where all nodes are transmitters and make contacts at
rate
λ
, the model reduces to a first-passage percolation model on th
e com-
plete graph with independent link-passage times, and the by
now classical
paper of Janson [
13
] shows that the broadcast time can be approximated by
T