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.

Rumor propagation Models

In the last few years, there has been a growing interest in rumor propagation in Online social networks problems where different approaches have been proposed to investigate it. By carefully scrutinizing the existing literature, we categorize the works into macroscopic and microscopic approaches.

Macroscopic models

The first category is mainly based on the Epidemic models where the pioneering research engaging rumor propagation under these models started during the 1960s.

epidemic models

A standard model of rumor spreading was introduced by Daley and Kendall, 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:

• I: people who are ignorant of the rumor;
• S: 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. 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.

${\begin{matrix}{}\\S+I{\xrightarrow {\alpha }}2S\\{}\end{matrix}}$ 1

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

${\begin{matrix}{}\\S+S{\xrightarrow {\beta }}S+R\\{}\end{matrix}}$ 2

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

${\begin{matrix}{}\\S+R{\xrightarrow {\beta }}2R\\{}\end{matrix}}$ 3

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\geq 0$ and ${dy \over dt}\leq 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.

Epidemic models 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 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$.

Microscopic models

The microscopic approaches attracted more attention in the individual's interaction: "who influenced whom." The known models in this category are the independent cascades (IC) and the linear threshold (LT) models , the energy model ,HISBmodel and Galam's Model .

HISBmodel

Considering the major role of the rumor propagation model in the problem of limiting its influence in OSNs, the main goal of this paper is to provide a propagation model that reproduces a realistic trend of this phenomenon and provide significant indicators to assess the impact of the rumor to better understand the diffusion process and reduce its influence. The variety of the human being makes their decision-making of spreading an information unpredictable, which is the primary challenge of modeling such a complex phenomenon. In order to model such a phenomenon that deal with human activities in OSN, it is significantly important to consider the impact of human individual and social behaviors in the spreading process. Thus, this section presents a rumor propagation model based on an analysis of the users' behaviors and their social interactions in a multiplex OSNs, named HISBmodel. Unlike the model of literature, our model focuses on how the individuals propagate a rumor in an OSN rather than how this information spread. In that, the model attempt to answers the following question: ``When an individual spread the rumor? when an individual accept the rumor? which OSN this individual will spread the rumor? . In this model, we introduce a formulation of individual behavior towards a rumor, which is analogous to the damped harmonic motion. Then, we present an integration of the opinion of individuals in this process, considering the social influence behaviors. Additionally, we establish rules of human social interaction between individuals, in which we place emphasis in which layer of the network the individual will spread the rumor. As a result, we describe the propagation process of rumors based on the HSIBmodel inspired from a real scenario in multiplex OSNs. Furthermore, we show that model allows us to present new metrics to evaluate the impact of the spread of a rumor; these metrics reflect an accurate state of the propagation of the rumor to evaluate its impact.

Multiplex Online Social Networks Representation

In literature, generally an OSN is considered as a directed or undirected graph G=(V, E) where the set of nodes $V$ represents the users and the set of edges $E$ can be seen as relationships among individuals. However, with the diversity of OSN, individuals usually join several OSNs at the same time in which each individual may have several accounts. Therefore, the information no longer spread in a single network but in a multiplex structure of OSNs. Thus, based on this idea and works in literature \cite{Kuhnle2018,zhang2016least}, we define a multiplex OSNs. \textbf{Definition 1 :} A multiplex OSNs with $n$ networks is a set \mathbb{G}^n = (I,G^n ) , where $I=(V,C)$ is the set of individuals represented in the center of Fig. \ref{fig:fig1} \todo{\textbf{Answer2.2:} The caption figures have been consolidated with addition information explaining the main idea behind each figure.} where for each individual $i\in I$ is represented by a node $v \in V$ and a set of characteristics $c \in C$. The characteristic of an individual defines its behaviors toward a rumor which will be defined in the following section( see section\ref{sec:32}). The set $G^n=\{ G_1=(V,E_1), $ $G_2=(V,E_2), ... ,G_n=(V,E_n)\}$ is a set of $n$ graphs, where $G_i=(V,E_i)$ is a directed graph representing an OSN; for example in Fig. \ref{fig:fig1}, $G^3=\{ G_1=(V,E_1), $ $G_2=(V,E_2),G_3=(V,E_3)\}$ are respectively Instagrame, Twitter and FaceBook networks represented by directed graph. . Without loss of generality, we consider each network of the multiplex has the same number of nodes. Therefore, if a node $v \in G_i$ does not belong to $G_j$, we add this node to $G_j$ as an isolated node presented in black colors in Fig. \ref{fig:fig1}.}

\subsection{Individual Behavior Toward a Rumor Formulation}

While analyzing the individual behavior in OSN, we are inspired by a model of physics that fits the description of the behaviors. We use the analogy that the attraction of an individual to a rumor is similar to an oscillator system when it is displaced from its equilibrium position. The individual's attraction to the rumor is initially large and then exhibits a gradual downtrend \cite{Yang2011a,Han2014}. Likewise, the amplitude of the motion is high in the beginning, and then decreases gradually, depending on the damping parameter. The damping parameter represents in this case the individuals' background knowledge (IBK) about the rumor, which can define the abilities of an individual to evaluate the trustworthiness of a rumor \cite{Afassinou2014}. Accordingly, the greater the IBK about the rumor is, the quicker the loss of interest on a rumor . However, due to the hesitating mechanism (HM), an individual can eventually have a latent time before spreading the rumor which is relatively related to the degree of doubt of individuals on the revived rumor \cite{Xia2015}. This factor is analogous to the phase of the system . Furthermore, during the propagation process, individuals can cease and restart transmitting the rumor due to the forgetting-remembering (FR) factor, which has been studied by \citet{Zhao2013a,Zhao2011,Zhao2012,Zhao2013} in various works . Therefore, we associate the FR to the individuals' addiction to OSNs, where the greater the time a user spends in an OSN, the more chances there are to remember the rumor. The FR is analogized as a system oscillating around its equilibrium position, where the oscillation frequency of the system represents the degree of the user's addiction to OSNs. This parameter represents the periodicity of an individual to switch between the forgetting and remembering phases. We can define the individual's attraction to a rumor as \begin{equation}\label{Equ:euq1}

A(t)=A_{int} e^{-\beta t} \cos(\omega t+\delta),

\end{equation}

\noindent where $A(t)$ is the attraction of the individual to the rumor at the time $t$,

$A_{int}$  is the initial attraction to the rumor,

$\beta$ represents the IBK, the FR factor $\omega$ represents the period of forgetting and remembering and $\delta$ is the HM factor that represents the degree of trust in the source of the rumor. In order to fit the proposed formulation to a real scenarios, we set $\delta'= \pi / 2 + \delta$ as a result the latent time of an individuals before spreading the rumor increases when $\delta$ increases. Finally, for non-negative values of the individual's attraction, we consider $A(t)=| A(t)|$. The individuals attraction to the rumor is presented as follows

\begin{equation}\label{Equ:euq1}

A(t)=A_{int} e^{-\beta t} |\sin(\omega t+\delta)|.

\end{equation}