Rumor spread in social network

Rumor is an important form of social communications, and spread of rumors plays a significant role in a variety of human affairs. There are two rumor models that are widely used, i.e. DK model and MK model. Particularly, we can view rumor spread as a stochastic process in social networks.

Model

Spread of Rumors

An standard model of rumor spreading was introduced by Daley and Kendall,^[1] which is called DK model. Assume there are N people in total. And those people in the network are categorized into three groups: ignorants, spreaders and stiflers, which are denoted as S, I, and R respectively hereinafter:

• S: people who are ignorant of the rumor;
• I: people who actively spread the rumor;
• R: people who have heard the rumor, but no longer are interested in spreading it.

The rumor is propagated through the population by pair-wise contacts between spreaders and others in the population. Any spreader involved in a pair-wise meeting attempts to “infect” the other individual with the rumor. In the case this other individual is an ignorant, he or she becomes a spreader. In the other two cases, either one or both of those involved in the meeting learn that the rumor is known and decided not to tell the rumor anymore, thereby turning into stiflers.

One famous variant is Maki-Thompson(MK) model.^[2] In this model, rumor is spread by directed contacts of the spreaders with others in the population. Furthermore, when a spreader contacts another spreader only the initiating spreader becomes a stifler. Therefore, three types of interactions can happen with certain rates.

1. $S+I\xrightarrow{\alpha}2I$
   

   which says when a spreader meet an ignorant, the ignorant will become a spreader.

2. $I+I\xrightarrow{\beta}I+R$
   

   which says when two spreaders meet with each other, one of them will become a stifler.

3. $I+R\xrightarrow{\beta}2R$
   

   which says when a spreader meet a stifler, the spreader will lose the interest in spreading the rumor, so become a stifler.

Of course we always have conservation of individuals:
$N=I+S+R$

The change in each class in a small time interval is:
$\Delta S \approx - \Delta t \alpha IS/N$
$\Delta I \approx \Delta t [{\alpha IS \over N} - {\beta I^2 \over N} - {\beta IR \over N}]$
$\Delta R \approx \Delta t [{\beta I^2 \over N}+{\beta IR \over N}]$

Since we know $S$, $I$ and $R$ sum up to $N$, we can reduce one equation from the above, which leads to a set of differential equations using relative variable $x=I/N$ and $y=S/N$ as follows
${dx \over dt} = x \alpha y - \beta x^2 - \beta x(1-x-y)$
${dy \over dt} = - \alpha xy$
which we can write ${dx \over dt} = (\alpha + \beta)xy - \beta x$
${dy \over dt} = - \alpha xy$

Compared with the ordinary SIR model, we see that the only difference to the ordinary SIR model is that we have a factor $\alpha + \beta$ in the first equation instead of just $\alpha$. We immediately see that the ignorants can only decrease since $x,y\ge 0$ and ${dy \over dt}\le 0$. Also, if
$R_0={\alpha +\beta \over \beta} >1$
which means
${\alpha \over \beta}>0$
the rumour model exhibits an “epidemic” even for arbitrarily small rate parameters.

Rumor Spread in Social Network

We model the process introduced above on a network in discrete time, that is, we can model it as a DTMC. Say we have a network with N nodes, then we can define $X_i(t)$ to be the state of node i at time t. Then $X(t)$ is a stochastic process on $S=\{S,I,R\}^N$. At a single moment, some node i and node j interact with each other, and then one of them will change its state. Thus we define the function $f$ so that for $x$ in $S$,$f(x,i,j)$ is when the state of network is $x$, node i and node j interact with each other, and one of them will change its state. The transition matrix depends on the number of ties of node i and node j, as well as the state of node i and node j. For any $y=f(x,i,j)$, we try to find $P(x,y)$. If node i is in state I and node j is in state S, then $P(x,y)=\alpha A_{ji}/k_i$; if node i is in state I and node j is in state I, then $P(x,y)=\beta A_{ji}/k_i$; if node i is in state I and node j is in state R, then $P(x,y)=\beta A_{ji}/k_i$. For all other $y$, $P(x,y)=0$.
The procedure^[3] on a network is as follows:

1. We initial rumor to a single node $i$;
2. We pick one of its neighbors as given by the adjacency matrix, so the probability we will pick node $j$ is
   

   $p_j={A_{ji} \over k_i}$
   

   where $A_{ji}$ is from the adjacency matrix and $A_{ji}=1$ if there is a tie from $i$ to $j$, and $k_i= \textstyle \sum_{j=1}^N A_{ij}$ is the degree for node $i$;
3. Then have the choice:
   1. If node $j$ is an ignorant, it becomes a spreader at a rate $\alpha$;
   2. If node $j$ is a spreader or stifler, then node $i$ becomes a stifler at a rate $\beta$.
4. We pick another node who is a spreader at random, and repeat the process.

We would expect that this process spreads the rumor throughout a considerable fraction of the network. Note however that if we have a strong local clustering around a node, what can happen is that many nodes become spreaders and have neighbors who are spreaders. Then, every time we pick one of those, they will recover and can extinguish the rumor spread. On the other hand, if we have a network that is small world, that is, a network in which the shortest path between two randomly chosen nodes is much smaller than that one would expect, we can expect the rumor spread far away.

Also we can compute the final number of people who once spread the news, this is given by
$r_\infty=1-e^{-({\alpha +\beta \over \beta})r_\infty}$
In networks the process that does not have a threshold in a well mixed population, exhibits a clear cut phase-transition in small worlds. The following graph illustrates the asymptotic value of $r_\infty$ as a function of the rewiring probability $p$.

References

1. Daley, D.J., and Kendal, D.G. 1965 Stochastic rumors, J. Inst. Maths Applics 1, p42.
2. Maki, D.P. 1973 Mathematical Models and Applications, With Emphasis on Social, Life, and Management Sciences, Prentice Hall.
3. Brockmann, D. 2011 Complex Networks and Systems, Lecture Notes, Northwestern University