Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Rumor Spreading and Inoculation of nodes inComplex Networks
Anurag Singh,Y N Singh
EE dept., IIT Kanpur, India

April 17, 2012

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

Table of contents
1

Introduction
Previous research

2Classic Rumor Spreading model: Nekovee et el.

3

Proposed Rumor Spreading ModelS I Racc Rrej vs time

4Random Inoculation on Small World Networkwith small average degreewith large average degree

5Targeted Inoculation on Small World Networkwith small average degreewith large average degree

6Conclusion

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Previous research

Introduction

In disaster, people try to acquire information through socialweb.
Social web information may be unreliable.
Harmful rumors spread and cause people to panic.
In information oriented society, a mechanism to suppress
harmful rumors in social web is very important.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Previous research

Introduction

Complex network is an important field of research.
Models e.g. ER model, small world network model, scale freenetwork model
similar as epidemic spreading in complex networks
Problem in rumor spreading to control the spread of rumor.
Successful control of rumor spreading means lifelong
inoculation.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Previous research

Introduction

In rumor spreading topology of network plays an importantrole.
Small world network model given by Watts Strogatz (WS)
as complex network model
WS model integrates the features of regular and randomgraphs together.
Starting with regular graph (e.g. a lattice ring) and randomly“rewiring” a given probability P of edges.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex NetworkIntroduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Previous research

Introduction
Intermediate values of P of the resulting graph has propertiesof a random graph (slowly growing diameter) and otherproperties resembling a regular graph (high clustering).
Small diameter and high clustering for this intermediate valueof P in small world network.
Nodes have similar degrees, i.e., the degree distribution has
small fluctuations, called homogeneous networks.(randomnetworks, regular networks and small world networks.)
Nodes with large fluctuations in degree distributions are called
heterogeneous. (scale free networks)

Anurag Singh,Y N Singh EE dept., IIT Kanpur, IndiaRumor Spreading and Inoculation of nodes in Complex NetworkIntroduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Previous research

DK and MK model
The rumor spreading can be seen as epidemic spreading as
contact network.
In Daley-Kendal (DK) homogeneous population is subdivided
into three groups:ignorant (who don’t know rumor),spreaders (who know rumor),
stifler (know rumor but not want to spread it).

Rumor propagated in the population by pairwise contacts.
Spreader involved in a pairwise meeting attempts to infectother individual.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Previous research

DK and MK model
If it is an ignorant, it becomes a spreader.
If it is spreader or stifler, meeting learn that rumor is known
and decide not to spread rumor, by turning into stifler.
In Maki Thomsan (MK) model when spreader contacts
another spreader only initiating spreader becomes a stifler.
Do not consider the topology of the underlying social
interconnection networks.
Restricted in explaining real world scenario for rumor
spreading.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Classic Rumor Spreading model
Nekovee, et al. proposed a model using Mean field equations
to describe the dynamics of the model.
The total population is divided into three compartments:(a) ignorants (b) spreaders (c) stifler
When a spreader contacts an ignorant, the ignorant becomesa spreader with rate λ.
(individuals to accept a rumor only with a certain probability,
depends upon the credibility of the rumor )when a spreader contacts another spreader or stifler theinitiating spreader becomes a stifler with rate γ.
(individuals to lose interest in spreading a rumor, when theylearn, contacts with others.)
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Classic Rumor Spreading model
For homogeneous networks Nekovee et el. proposed following
rumor equations:dI (t)dtdS(t)dtdR(t)dt= −λhkiI (t)S(t),= λhkiI (t)S(t) − γhkiS(t)(S(t) + R(t)),= γhkiS(t)(S(t) + R(t))

where, I (t), S(t) and R(t) are the fraction of ignorant nodes,
spreaders and stifler respectively and,I (t) + S(t) + R(t) = 1
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India(1)

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

S I Racc Rrej vs time

Proposed Rumor Spreading Model

Stifler have been further divided into two compartments:
Stifler who accept the rumor
Stifler who reject the rumor

Here I (t), S(t), Racc (t), Rrej (t) are the fraction of ignorant,
spreaders, stifler who accept the rumor and stifler who rejects
the rumor.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex NetworkIntroduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

S I Racc Rrej vs time

Pairwise contacts
Rumor spreading process can be summarized by following setof pairwise interaction.
I (t) + S(t) + Racc (t) + Rrej (t) = 1,(2)λI +S −→ 2S,
δ→ Rrej + S,
I +S −
α

I +S −→ Racc + S,
γ

S + Racc −→ 2Racc ,γ

S + Rrej −→ Racc + Rrej ,γS +S −→ Racc + S.
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading ModelRandom Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

S I Racc Rrej vs time

Rumor Equations
Mean field rate equations for our model asdI (t)dtdS(t)dt= −(λ + α + δ)hkiI (t)S(t),= λhkiI (t)S(t) − γhkiS(t)(S(t) + Racc (t) +Rrej (t)),

dRacc (t)dt

= γhkiS(t)(S(t) + Racc (t) + Rrej (t)) +αhkiI (t)S(t),dRrej (t)= δhkiI (t)S(t).
dtR(t) = Racc (t) + Rrej (t).

(3)
(4)

where, hki is the average degree of the WS network
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

S I Racc Rrej vs time

Rumor equations

Initial conditions, I (0) ≈ 1, S(0) ≈ 0, Racc (0) = 0, Rrej (0) = 0and λ + α + δ ≤ 1.
Solving rumor equations :R(∞) = 1 − e− λ+γ
R(∞)
γ(5)

where, R(∞) = limt→∞ R(t) and R(∞) = Racc (∞) + Rrej (∞)

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

S I Racc Rrej vs time

110.9

0.9

0.8

0.8

fraction of spreaders nodes

fraction of ignorant nodes

S I Racc Rrej vs time

0.7

0.6

0.5

0.4

0.3

0.2

0.6

0.5

0.4

0.3

0.2

0.1

00.7

0.1

05

10

152025

30

3540

45

50

005

1015

2025

timetime

(a)

(b)

30

3540

45

50

Figure: (a) Fraction of Ignorants (b) fraction of Spreaders against time by using
λ = 0.35, γ = 0.38, α = 0, δ = 0.12, hki = 4 and N =10000

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

S I Racc Rrej vs time

1

1

0.9

0.9

0.8

0.8

fraction of stifler nodes (reject rumor)

fraction of stifler nodes (accept rumor)

S I Racc Rrej vs time

0.7

0.6

0.5

0.4

0.3

0.2

0.1

00.7

0.6

0.5

0.4

0.3

0.2

0.1

05

1015202530

3540

45

50

00510152025timetime(c)(d)

3035404550

Figure: (c) Fraction of Stifler who accept rumor (d) fraction of Stifler who rejectrumor against time by using λ = 0.35, γ = 0.38, α = 0, δ = 0.12, hki = 4 and N=10000
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

S I Racc Rrej vs time

S I Racc Rrej vs time
From rumor equations:
Racc (∞) =Rrej (∞) =Racc (∞)
Rrej (∞)=α+λR(∞)
δ+α+λδ
R(∞)
δ+α+λα+λδ

Increase δ (decrease the acceptability) and fix otherparameters, Racc (∞) will decrease.
Decrease the acceptability of the rumor, density of
populations who accept the rumor will also decrease.
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

Random Inoculation on Small World Network

g is the fraction of inoculative nodes.
Initial conditions modified asI (0) ≈ 1 − g , S(0) ≈ 0, Racc (0) = 0, Rrej (0) = g .
We will get:λ+γR(∞) = 1 − (1 − g )e γ

Anurag Singh,Y N Singh EE dept., IIT Kanpur, Indiag − λ+γR(∞)γe(6)

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

Random Inoculation on Small World Network

Through simulation and theory that g is the only non zero
solution of R(∞).
λFind critical inoculation of g is gc = λ+γ.

Therefore Racc = 0 at gc , random inoculation can makeaccepted rumor density to 0.
Analysis can be validate by numerical simulation on WSmodel.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

IntroductionClassic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

with small average degree

density of stifles who accepted rumor Racc(∞)

Result using N=10,000, hki = 4 and rewiring probability(P)=0.8 on WS model, λ = 0.25, α = 0, δ = 0 and γ = 0.25
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

density of inoculation nodes(g)Figure: Comparison between Racc and density of inoculation nodes g in random
inoculation with small degree 4.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

with large average degree

density of stifles who accepted rumor Racc(∞)

To describe rumor equations correctly0 ≤ (λ + α + δ)hkiS(t) ≤ 1 and0 ≤ γhki(S(t) + Racc (t) + Rrej (t)) ≤ 1
When hki is too large, these constraints will fail as in Figure.
10.9

δ=0
δ=0.25
δ=0.5
δ=0.75

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

density of inoculation nodes(g)Figure: Comparison between Racc and density of inoculation nodes g in random
inoculation with large degree 12.
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

with large average degree

Rumor equations are not be accurate when hki is large. Thus
random inoculation is no longer efficient.
It can be solved by increasing the parameter δ (decrease theacceptability of rumor) and apply random inoculation method
at same time.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World NetworkConclusion

with small average degree

density of stifles who accepted rumor Racc(∞)

When high-degree node is inoculated, the effective degree of
its neighbors drops
For small hki it can be seen in figure that target inoculation isbetter than the random inoculation,
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00

0.05

0.1

0.15

0.2

0.25

0.3

0.35

density of inoculation nodes(g)Figure: Comparison between Racc and density of inoculation nodes g in targetedinoculation with small degree 4.
Anurag Singh,Y N Singh EE dept., IIT Kanpur, IndiaRumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

with large average degree

density of stifles who accepted rumor Racc(∞)

When hki is large, targeted inoculation is not effective.
Increase δ with targeted inoculation, rumor spreading can besuppressed.
1

δ=0
δ=0.25
δ=0.5
δ=0.75

0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
000.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

density of inoculation nodes(g)Figure: Comparison between Racc and density of inoculation nodes g in targeted
inoculation with large degree 12.
Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World NetworkTargeted Inoculation on Small World Network
Conclusion

Conclusion
New compartment of nodes as stifler who rejects the rumor
with rate δ is added
Model supports the small critical inoculation value gc inrandom and targeted inoculation for small hki .
In targeted inoculation that gc is smaller than random
inoculation when hki is small.
For large hki alone random or targeted inoculation will not beeffective.
Decrease the acceptability of the rumor and apply on therandom or targeted inoculation method simultaneously.

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network

Introduction
Classic Rumor Spreading model: Nekovee et el.
Proposed Rumor Spreading Model
Random Inoculation on Small World Network
Targeted Inoculation on Small World Network
Conclusion

Thank You
Questions ?

Anurag Singh,Y N Singh EE dept., IIT Kanpur, India

Rumor Spreading and Inoculation of nodes in Complex Network