Rumor spread in social network

The spread of rumors is an important form of communication in society. There are two approaches to investigating the rumor spreading process: microscopic models and the macroscopic models. The macroscopic models propose a macro view about this process and are mainly based on the widely-used Daley-Kendall and Maki-Thompson models. Particularly, rumor spread can be viewed as a stochastic process in social networks. By contrast, the microscopic models are more interested on micro-level interactions between individuals.

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.

Macroscopic models

The first category is mainly based on the epidemic models. Pioneering research on rumor propagation using these models started during the 1960s.^[1]

Epidemic models

A standard model of rumor spreading was introduced by Daley and Kendall.^[1] 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 (in correspondance with the SIR model):

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

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 variant is the Maki-Thompson 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.

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

1

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

${\displaystyle {\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.

${\displaystyle {\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:

${\displaystyle N=I+S+R}$

The change in each class in a small time interval is:

${\displaystyle \Delta S\approx \Delta t[{\alpha IS \over N}-{\beta S^{2} \over N}-{\beta SR \over N}]}$

${\displaystyle \Delta I\approx -\Delta t\alpha IS/N}$

${\displaystyle \Delta R\approx \Delta t[{\beta S^{2} \over N}+{\beta SR \over N}]}$

Since we know ${\displaystyle S}$, ${\displaystyle I}$ and ${\displaystyle R}$ sum up to ${\displaystyle N}$, we can reduce one equation from the above, which leads to a set of differential equations using relative variable ${\displaystyle x=I/N}$ and ${\displaystyle y=S/N}$ as follows

${\displaystyle {dx \over dt}=x\alpha y-\beta x^{2}-\beta x(1-x-y)}$

${\displaystyle {dy \over dt}=-\alpha xy}$

which we can write

${\displaystyle {dx \over dt}=(\alpha +\beta )xy-\beta x}$

${\displaystyle {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 ${\displaystyle \alpha +\beta }$ in the first equation instead of just ${\displaystyle \alpha }$. We immediately see that the ignorants can only decrease since ${\displaystyle x,y\geq 0}$ and ${\displaystyle {dy \over dt}\leq 0}$. Also, if

${\displaystyle R_{0}={\alpha +\beta \over \beta }>1}$

which means

${\displaystyle {\alpha \over \beta }>0}$

the rumor model exhibits an “epidemic” even for arbitrarily small rate parameters.

Epidemic models in social networks

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 ${\displaystyle X_{i}(t)}$ to be the state of node i at time t. Then ${\displaystyle X(t)}$ is a stochastic process on ${\displaystyle 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 ${\displaystyle f}$ so that for ${\displaystyle x}$ in ${\displaystyle S}$,${\displaystyle f(x,i,j)}$ is when the state of network is ${\displaystyle 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 ${\displaystyle y=f(x,i,j)}$, we try to find ${\displaystyle P(x,y)}$. If node i is in state I and node j is in state S, then ${\displaystyle P(x,y)=\alpha A_{ji}/k_{i}}$; if node i is in state I and node j is in state I, then ${\displaystyle P(x,y)=\beta A_{ji}/k_{i}}$; if node i is in state I and node j is in state R, then ${\displaystyle P(x,y)=\beta A_{ji}/k_{i}}$. For all other ${\displaystyle y}$, ${\displaystyle P(x,y)=0}$.

The procedure on a network is as follows:^[3]

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

   ${\displaystyle p_{j}={A_{ji} \over k_{i}}}$
   

   where ${\displaystyle A_{ji}}$ is from the adjacency matrix and ${\displaystyle A_{ji}=1}$ if there is a tie from ${\displaystyle i}$ to ${\displaystyle j}$, and ${\displaystyle k_{i}=\textstyle \sum _{j=1}^{N}A_{ij}}$ is the degree for node ${\displaystyle i}$;
3. Then have the choice:
   1. If node ${\displaystyle j}$ is an ignorant, it becomes a spreader at a rate ${\displaystyle \alpha }$;
   2. If node ${\displaystyle j}$ is a spreader or stifler, then node ${\displaystyle i}$ becomes a stifler at a rate ${\displaystyle \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
${\displaystyle 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 ${\displaystyle r_{\infty }}$ as a function of the rewiring probability ${\displaystyle p}$.

Microscopic models

The microscopic approaches are more focused on interactions between individuals: "who influenced whom."

Models include the independent cascade model, linear threshold model,^[4] energy model,^[5] HISBmodel,^[6] and Galam's Model.^[7]

Independent cascades models

Independent Cascade (IC) Model

The Independent Cascade (IC) model is a probabilistic framework for modeling the spread of influence through a social network. In this model, the diffusion process unfolds in discrete time steps. When a node becomes active (i.e., influenced), it has a single chance to activate each of its inactive neighbors. The activation attempt succeeds with a certain probability, specific to the edge connecting the nodes. If the attempt fails, the neighbor cannot be activated by that node in future steps. This process continues until no more activations are possible.

Mathematically, the probability that an active node u activates an inactive neighbor v is denoted as ${\displaystyle p_{uv}}$. The activation process can be described as follows:

1. At time ${\displaystyle t=0}$, a set of seed nodes ${\displaystyle A_{0}}$ are activated.
2. For each subsequent time step ${\displaystyle t\geq 1}$, any node ${\displaystyle u}$ that became active at time ${\displaystyle t-1}$ has one chance to activate each inactive neighbor ${\displaystyle v}$, with probability ${\displaystyle p_{uv}}$.
3. If ${\displaystyle v}$ is activated, it becomes active at time ${\displaystyle t}$; otherwise, it remains inactive.
4. The process continues until no new activations occur.

This model captures scenarios where individuals independently decide to adopt a behavior or product after being influenced by their peers. It is particularly useful for modeling viral marketing and information dissemination in networks.

^[8]

Linear threshold models

The Linear Threshold (LT) model is another approach to modeling influence spread in social networks. In this model, each node is assigned a threshold value, representing the fraction of its neighbors that need to be active before it becomes active itself. Each edge from a neighbor to a node has an associated weight, indicating the strength of influence. The sum of incoming edge weights to a node is typically constrained to be at most 1.

Mathematically, for a node ${\displaystyle v}$, let ${\displaystyle N(v)}$ be the set of its neighbors, and ${\displaystyle w_{uv}}$ be the weight of the edge from neighbor ${\displaystyle u}$ to ${\displaystyle v}$, such that ${\displaystyle \sum _{u\in N(v)}w_{uv}\leq 1}$. Each node ${\displaystyle v}$ is assigned a threshold ${\displaystyle \theta _{v}}$, drawn uniformly at random from the interval [0,1].

The activation process proceeds as follows:

1. At time ${\displaystyle t=0}$, a set of seed nodes ${\displaystyle A_{0}}$ are activated.
2. For each subsequent time step ${\displaystyle t\geq 1}$, any inactive node ${\displaystyle v}$ becomes active if the total weight of its active neighbors meets or exceeds its threshold:

${\displaystyle \sum _{u\in A_{t-1}\cap N(v)}w_{uv}\geq \theta _{v}}$

1. The process continues until no new activations occur.

The LT model reflects situations where individuals adopt behaviors based on the collective influence of their peers, such as adopting a new technology or participating in social movements.

^[8]

Energy model

HISB Model

In recent years, the rampant spread of misinformation and rumors on online social networks (OSNs) has raised significant concerns within the scientific and technological communities. OSNs are powerful tools for disseminating information, but they can also accelerate the propagation of false or misleading content, which may have serious societal consequences. Consequently, the study of rumor dynamics and the development of effective mitigation strategies have become crucial areas of research.

Several models have been proposed to analyze and control rumor spread in OSNs. Among them, the HISB model (Human Individual and Social Behavior model) stands out as a comprehensive approach that incorporates both individual cognitive factors and social influence mechanisms. This model was first introduced in ^[9], where the authors proposed a rumor diffusion framework based on human behaviors in online social environments. It was later refined and applied in a more practical context for rumor mitigation in ^[10].

Subsequent enhancements were made in ^[11], where the model was adapted for breaking news scenarios, addressing the challenges of real-time rumor control. Most recently, a hybrid approach incorporating the HISB model was proposed by ^[12].

These successive contributions illustrate the robustness and adaptability of the HISB framework in tackling the evolving nature of misinformation in OSNs. This article provides a comprehensive overview of rumor propagation models, with a focus on those incorporating behavioral dynamics, and discusses state-of-the-art strategies for minimizing rumor influence.

This article adopts the HISBmodel for simulating rumor diffusion. Below, we provide an overview of its key components.

Individual Behaviors Toward Rumors

The HISBmodel represents the behavior of individuals facing a rumor through three main factors:

1. Background Knowledge (\$\beta\$): Reflects an individual's knowledge of the rumor's topic, influencing their judgment of its credibility.

1. Hesitation Mechanism (\$\delta\$): Represents the delay before spreading a rumor, modeling skepticism or doubt.

1. Forgetting-Remembering Factor (\$\omega\$): Linked to the user's engagement with the OSN platform and their likelihood of recalling the rumor.

An individual's attraction to a rumor over time is modeled after damped harmonic motion:

${\displaystyle A\_u(t)=A\_{int}^{u}e^{-\beta \_ut}\left|\sin(\omega \_ut+\delta \_u)\right|}$

where ${\displaystyle A\_u(t)}$ is the attraction of user ${\displaystyle u}$ to the rumor at time ${\displaystyle t}$, and ${\displaystyle A\_{int}^{u}}$ is the initial attraction.

Propagation Process in Multilayer Networks

The model operates on a dynamic multilayer graph ${\displaystyle {G\_1}\_t,\ldots ,{G\_n}\_t}$, where each layer represents a different OSN or mode of interaction over time ${\displaystyle t\in {0,1,\ldots ,T}}$. Each user can be in one of three states:

• Ignorant: Not yet exposed to the rumor
• Spreader: Currently spreading the rumor
• Stifler: No longer spreading the rumor

At each time step ${\displaystyle t-1}$, spreaders may transmit the rumor according to one of two models:

1. One2One Model (${\displaystyle \sigma '}$): A spreader chooses one random neighbor to contact.

1. One2Many Model (${\displaystyle \sigma }$): A spreader contacts a subset of its neighbors.

The probability of rumor transmission from node ${\displaystyle u}$ to ${\displaystyle v}$ on layer ${\displaystyle i}$ at time ${\displaystyle t}$ is given by:

${\displaystyle p\_{u,v,i}(t)=p\_u^{send}(t)\cdot (p\_u)*i\cdot (p*{v,u}^{acc})\_i}$

With the components defined as:

${\displaystyle p\_u^{send}(t)=e^{-\beta \_ut}|\sin(\omega \_ut+\delta \_u)|}$

${\displaystyle (p\_u)*i={\frac {(d*{in})*i(u)}{\sum *{j=1}^{k}(d\_{in})*j(u)}}}$

${\displaystyle (p*{v,u}^{acc})*i={\frac {1}{1+{\frac {(d*{in})*i(v)}{(d*{in})\_i(u)}}}}\cdot P}$

where ${\displaystyle P}$ is a tunable propagation probability and ${\displaystyle (d\_{in})\_i(u)}$ is the in-degree of ${\displaystyle u}$ in layer ${\displaystyle i}$.

The global popularity of the rumor is measured as:

${\displaystyle R(t)=\sum \_{i=1}^{n}R\_i(t),\quad {\text{where}}\quad R\_i(t)=\sum \_{v\in V}A\_v(t)\cdot (d\_{in})\_i(v)}$

The rumor ceases to propagate when ${\displaystyle R(t)\approx 0}$.

Individual Opinion Dynamics

Individuals' opinions evolve using a discrete-time Markov chain with states:

• Supporting (S)
• Questioning (Q)
• Neutral (N)
• Denying (D)

Each node ${\displaystyle v}$ has a transition matrix:

${\displaystyle P_{v}={\begin{bmatrix}1-\rho &{\frac {\rho }{2}}&{\frac {\rho }{2}}&0\\{\frac {1-\rho }{3}}&{\frac {1-\rho }{3}}&{\frac {1-\rho }{3}}&\rho \\{\frac {1-\rho }{3}}&{\frac {1-\rho }{3}}&{\frac {1-\rho }{3}}&\rho \\0&{\frac {1-\rho }{2}}&{\frac {1-\rho }{2}}&\rho \\\end{bmatrix}}}$

The decision factor ${\displaystyle \rho }$ is given by:

${\displaystyle \rho ={\frac {n\_v^{-}}{n\_v}}\cdot J\_v}$

where ${\displaystyle n\_v^{-},n\_v}$ are the numbers of negative and total received rumors, and ${\displaystyle J\_v}$ reflects personal judgment.

The steady-state probability of denying a rumor is:

${\displaystyle \pi \_D(\rho )={\frac {\rho ^{2}-2\rho +1}{\rho ^{2}+\rho +1}}}$

Denoting ${\displaystyle \pi \_v^{-}=\pi \_D(\rho \_v)}$ and ${\displaystyle \pi \_v^{+}=1-\pi \_v^{-}}$, the model can predict long-term belief adoption.

This enhanced HISBmodel framework thus enables nuanced, multilayer-aware modeling of how rumors spread and opinions evolve across interconnected OSNs.

References

1. Daley, D.J., and Kendal, D.G. 1965 Stochastic rumors, J. Inst. Maths Applics 1, p. 42.
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
4. [1] D. Kempe, J. Kleinberg, É. Tardos, Maximizing the spread of influence through a social network, Proc. Ninth ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. - KDD ’03. (2003) 137. doi:10.1145/956755.956769.
5. S. Han, F. Zhuang, Q. He, Z. Shi, X. Ao, Energy model for rumor propagation on social networks, Phys. A Stat. Mech. Its Appl. 394 (2014) 99–109. doi:10.1016/j.physa.2013.10.003.
6. A.I.E. Hosni, K. Li, S. Ahmed, HISBmodel : A Rumor Diffusion Model Based on Human Individual and Social Behaviors in Online Social Networks, in: Springer, 2018.
7. S. Galam, Modelling rumors: The no plane Pentagon French hoax case, Phys. A Stat. Mech. Its Appl. 320 (2003) 571–580. doi:10.1016/S0378-4371(02)01582-0.
8. Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the Spread of Influence through a Social Network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 137–146). https://doi.org/10.1145/956750.956769
9. A.I.E. Hosni, K. Li, S. Ahmed, HISBmodel : A Rumor Diffusion Model Based on Human Individual and Social Behaviors in Online Social Networks, in: Springer, 2018.
10. A.I.E. Hosni, K. Li, S. Ahmed, Minimizing rumor influence in multiplex online social networks based on human individual and social behaviors, in: Elsivier, 2019 Information science .
11. A.I.E. Hosni, K. Li, Minimizing the influence of rumors during breaking news events in online social networks, in: Elsivier, 2019 knowledge based systems .
12. Hosni, A.I.E., Baira, I., Merini, H. et al. Efficient hybrid rumor mitigation in dynamic and multilayer online social networks. Soc. Netw. Anal. Min. 14, 224 (2024). https://doi.org/10.1007/s13278-024-01381-z