Sociology Mind
2012. Vol.2, No.4, 477-481
Published Online October 2012 in SciRes (http://www.SciRP.org/journal/sm) http://dx.doi.org/10.4236/sm.2012.24061
Rumor Spreading and Degree-Related Preference Mechanism
on a Small-World Network*
Zhi Zhu, Fengjian Liu, Dongsheng Liao
Humanities and Social Sciences School, National University of Defense Technology, Changsha, China
Received July 3rd, 2012; revised August 6th, 2012; accepted August 19th, 2012
An alternate model for rumor spreading over small-world networks is suggested, of which two rumors
(termed rumor 1 and rumor 2) have different nodes and probabilities of acceptance. The propagation is
not symmetric in the sense that when deciding which rumor to adopt, high-degree nodes always consider
rumor 1 first, and low-degree nodes always consider rumor 2 first. The model is a natural generalization
of the well-known epidemic SIS model and reduces to it when some of the parameters of this model are
zero. We find that rumor 1 (preferred by high-degree nodes) is dominant in the network when the degree
of nodes is high enough and/or when the network contains large clustered groups of nodes, expelling ru-
mor 2. However, numerical simulations on synthetic networks show that it is possible for rumor 2 to oc-
cupy a nonzero fraction of the nodes in many cases as well. Specifically, in the NW small-world model a
moderate level of clustering supports its adoption, while increasing randomness reduces it.
Keywords: Rumor; Degree-Related Preference Mechanism; Small-World Network
Introduction
Rumor spreading is a complex socio-psychological process.
Pioneering contributions to their modeling, based on epidemi-
ological models, date back to (Landahl, 1953; Rapoport, 1952).
In those days both deterministic models and stochastic models
were used, and the former were so simple that they were solved
analytically and regarded as the first approximation of the latter.
To above study, Daley and Kendall (Daley, 1965) explained the
importance of dealing with stochastic rumor models rather than
deterministic ones, henceforth stochastic models have been
actively studied (Cane, 1966; Sudbur, 1985; Watson, 1987).
The basic rumor spreading model which they used is called
Daley-Kendall model after Daley (Daley, 1965).
The most popular model for information or rumor spreading,
introduced by Daley and Kendall (Daley, 1964) is conceptually
similar to the SIR model for epidemiology. Other widely used
models for describing collective social behavior are the thresh-
old models, first proposed by Granovetter in (Granovetter,
1978). Each individual has a specific threshold, based on which
a binary decision is made. More formal definitions which take
social network structure into account have appeared since, the
simplest version of which is the linear threshold model (Kempe,
2003). A variant of the threshold model has been used, for ex-
ample, in (Guardiola, 2002) for describing diffusion of innova-
tions in a population, and the effects of network topology have
been analyzed by Yunhao Liu (Liu, 2011).
However, the co-hypothesis of above research is that only
one type of rumor spreads through networks. In this paper we
propose a model of rumor spreading, where two different types
of rumor affect the nodes, and consider the behavior of the
model on a small-world network.
Our model follows this idea of the SIS epidemiological
model. Nodes are divided into three classes: ignorants, rumor 1
spreaders, and rumor 2 spreaders. Namely, each node is “sus-
ceptible” to the effects of two kinds of “infections” and is able
to recover from them as well. Moreover, the source of rumor 1
and rumor 2 both have special meaning, and some nodes will
always consider one of them first. This formulation could be
significant for describing four w-o-m processes circulating in a
social network. For example, when two opposing information
appear at the same time, both of them have a special meaning in
the public eye. But high degree means the one can get informa-
tion more, easier and more quickly (Christley, 2005), to get the
reality and choose which information to believe.
Finally, we outline a study which is close to our work in the
sense that two rumor types spread through the network. Namely,
in (Goldenberg, 2007), Goldenberg investigated the effects of
both positive and negative w-o-m on a firm’s profits. In this study,
negative w-o-m is limited to traveling two hops away from its
source. Trpevski (Trpevski, 2010) made an advance to investi-
gate both rumor types with different probabilities of acceptance.
In this study, rumor 1 is limited to be considered first. In our
model, both rumors can be selected by different types of nodes.
We structure the paper as follows. After defining the model
fully, we analyze the stability of its dynamics in Rumor
Spreading Model. In Behavior of the Model on Small-World
Network we describe the behavior of the model on NW
small-world topology and confirm, via further analysis and
dissemination simulations, a number of our calculations. We
offer some concluding remarks and points out potential re-
search directions in Conclusions and Discussion.
Rumor Spreading Model
Definition of the Model
*This work was supported in part by the National Natural Science Founda-
tion of China under Grant 91024030 (Modeling crowd psychology and
behaviors based on multi-agent theory for commonality secure). Consider a clustered populations composed by N individuals,

Z. ZHU ET AL.
connected by a interaction structure which is represented by
graph G = (V, E), with V and E denote the node and the edges,
respectively. A denotes the adjacency matrix of the graph G,
and aij = 1 if


,ij E and aij = 0 otherwise. Our model is a
discrete stochastic model, describing rumor spreading in a
small-world network. There are two different types of rumor
(rumor 1 and rumor 2) spreading from two different sources. At
time k, each node I only adopts one of three possible states: 1, 2,
and 3. The state of the node is indicated by a status vector,
 
123 ,1,,.
T
iiii
s
kskskski N




State 1 or 2 signifies that there is a adopter or spreader of
rumor 1 or 2. A node being in state 3 indicates it is a neutral in
relation to the two rumors. Every status vector above is com-
prised by two sub-states, which denote the degree of nodes.
Suppose


1j
i
s
k or


2j
i
s
k (j = 1, 2, 3) be the status vector
of node i, signifying it is a high-degree or low-degree node in
state j. The state of node i becomes
 
11112
,
iii
s
ksksk

 ,
 
22122
,
iii
s
ksksk

 ,
 
33132
,
iii
s
ksksk

 ,
i.e.,
 
12
,
jjj
iii
s
ksksk



(j = 1, 2, 3).
Let 





3131 3
ii
ksksk ,








3232 332
1
ii
kskskk 
be the fraction of nodes with high or low degree in state 3, with

31
i1
N
ii
s
kd



,
di = 1 if degre ei ≥ m0, otherwise, di = 0. The critical degree m0,
distinguishing the high-degree nodes from low-degree nodes, is
defined according to special situation. In a given network, both
of the fractions are calculable though simulation. In order to
facilitate the mathematical analysis, we rewrite


31 k and


32 k as


k and .

1k
Suppose the probability mass function of node i is
 
123
,,
iiii
pkpk p k pk


at time k. For every node i it states the probability of being in
each potential state at time k. Then the dynamics equations of
each node, i.e., the evolution of the model can be defined as
 

 


13132 1
1
11
iiiiiii
pkskfskg fask 










23132 2
2
11
iiiiiii
p
kskfgskgas k






  


  
3
31 32
12
12
31
12
1
11 11
11
11 11
i
iiii ii
ii
iii ii
pk
skfg skgf
aska sk
2
s
kf gaskask


 
 
(1)
 
1 MultiRealize1
TT
ii
sk pk

 

So, Equation (1) could be













13 3
1
1
11
,
iiii
i
pkkskfkskg f
as k



1
ii














23 3
2
111
iiiiii
pkkskfgkskg ask 
 2
i


 

  

   
    
3
33
12
12
31
12
1
11 11
11 1
11 11
i
iiii i
ii i
iii ii
pk
ks kfgk s kg
faskask
2
s
kf gaskask

 

 
(2)
 
1 MultiRealize1
JJ
ii
sk pk

 

.
Here, MultiRealize[·] performs the realization for probability
distribution given with


1
J
i
pk，a1 and a2 are parameters
(


12
,0,aa
N
1). We define fi and gi as
 
1
1
11
ii
j
jj
f
ks

k


 


,
 
2
1
11
N
ii
j
jj
g
ks 


 

k
]
.
(3)
In Equation (3), β and γ are parameters (). If a2 = 0, γ
= 0,
,[0,1



1k

 and no node in status 2 initially, a discrete stochas-
tic SIS model can be obtained as a special case of our model. Then
Status 1 and status 3 is the infective or susceptible state respec-
tively, with the curing rate being (Trpevski, 2010).
1
The degree-related preference mechanism of spreading is the
following. All nodes in status 1 try to spread rumor 1 to all of
their neighbors at time k, with probability β and the transmittals
are independent of other. All nodes in status 2 also send rumor
2 to all of their neighbors with probability γ. Therefore, fi and gi
are the probabilities that node i receives rumor 1 or rumor 2
from its neighbor supporting rumors 1 or 2, accordingly. How-
ever, note from the formulation of Equation (2) that node i with
high degree will become an adopter of rumor 2 at (k + 1) only if,
at time k, it does not receive a rumor 1 from its neighbors, or
node i with low degree will become an adopter of rumor 1 at (k
+ 1) only if, it does not receive rumor 2. More precisely, the
probability of high-degree nodes converting from an undecided
status 3 to status 1 is not fi, but multiplied by (1 − gi) which in
general is smaller than 1. Conversely, node i with high degree
can become an adopter of rumor 1 regardless of whether it re-
ceives rumor 2 or not. It is the same to nodes with low-degree
nodes. In this way, our model has performed two preferences in
each node for the rumor 1 and 2. Additionally, after supporting
a particular kind of rumor, the nodes in state 1 or 2 continue to
reserve their status with a rate of a1 or a2, respectively, i.e., they
convert back to status 3 at a rate of (1 − a1) or (1 − a2). Hence,
parameters a1 and a2 signify the remembrance rate of each ru-
mor, or how long nodes want to support the adopted rumor
before abandoning it and converting back to undecided status
(see Figure 1).
1a 
Our model is potentially suitable for a number of real-world
situations. In a structured organization, when a grave even
happened, managers with high degree, having more number of
contacts with different people and shorter path between other
individuals, can get more information about the reality and
adopt a kind of information. However, employees with low
degree, can not get the first hand information, and would like to
support an opposing rumor. In marketing circumstances, one
478

Z. ZHU ET AL.
can imagine two products competing for the market share with
similar customer orientation. Therefore, it is safe to use our
model to simulate the spread of word-of-mouth about two op-
posing information from different spreader, or two different
products.
Suppose the total number of nodes in statuses 1, 2, and 3 at
time k, be
 
1
1
N
i
i
X
ks

k
,
 
2
1
N
i
i
Yks k


and
 
3
12
1
N
i
i
Z
kskZkZ


k
respectively. Suppose the number of high degree and low de-
gree nodes in stratus 3 be
 
1
1
1
N
j
ji
i
Z
ks

k ,
 
2
2
1
N
j
ji
i
Z
ks

k, (j = 1, 2, 3),
respectively. Suppose


1
NEX 

, , and

2
NEY



33132
N
EZNN
 ,

11jj
NEZ  

,


22jj
NEZ


 
, (j = 1, 2, 3).
The object of interest is the average number of nodes that
eventually (when ) support statuses 1 and 2, N1, N2, N3,
Nj1 and Nj2, (j = 1, 2, 3),compared to the total number of nodes
N and N3, respectively, in the network.
k
In order to facilitate the mathematical analysis, we rewrite
our model as















13 3
1
1
11
iiii
i
pkkpkfkpkg f
ap k
 

1
ii















23
2
2
111
iiii
i
pkkpkfgkpkg
ap k
 

3
ii
(4)













33
1
2
2
1111
1
iiii
i
pkpk fgapk
apk


1
i
And fi, gi and


k as
 
1
1
11
N
ii
j
jj
f
ka


 

pk
jj
 
2
1
11
N
ii
j
g
kap

k


 


 (5)
 

31
3
i
i
s
k
k
s
k

11
i
s
12
i
s
1
i
s
21
i
s
22
i
s
2
i
s
31
i
s
32
i
s
3
i
s
1
a
1
1a
2
a
2
1a
i
f
(1 )
ii
g
f
i
g
(1 )
ii
f
g
Figure 1.
The model of rumor spreading with degree-related preference mecha-
nism.
Equivalently N1, N2, N3, Nj1 and Nj2, (j = 1, 2, 3), can be com-
puted with Equation (3) as

1
1
1
i
i
Np

N


,

2
2i
i
Np
1
N



,

3
3i
Np
,
1
N
i

1
1
1
N
jj
i
Nkp

ji


,



1
2
1
1
N
jj
ji
i
Nkp


 
, (j 2, 3).
Dynamical Systems Approach
To simulate our model better, we adopt a dynamical systems
e probabilities for the
ation (4) with
= 1,
approach to the model. We replace th
node i to support rumor 1 and 2 in Equ1
ii
x
p

and 2
ii
yp, respectively. The evolution of our model can be
rewritten as
 

1
1
11 11
1
ii iii
ii



2
2
11
i
iiii
x
kxkykgfaxk
yk
  


(6)
xkykfgayk 

and
jj
 
1
11
N
ii
j
f
ka


 

 xk
jj
 
2
1
11
N
ii
j
g
kay


 

k (7)
 

31
3
i
i
s
k
k
s
k

Equation (6) denotes a nonlinear dynamical system
F: [0, 1]2N → [0, 1]2N. Since xi and yi probabilities, and as-
suming that the corresponding graph is connected, then the
er guaran-
are
godicity of the Markov chain of the whole system is
teed, if 12
,1,,1aa

  .
Therefore, when condition (8) is satisfied, dynamical system
(6) has a unique globally stable fixed point. System (6) has a
fixed poi.
Chakrabar
int at (xi, yi) = (0, 0) for all
ti and Draief etc have already been proved the ex-

Z. ZHU ET AL.
istence of a network threshold 1

in several epidemiological
models of virus spreading e.g. SIS model and SIR model
(Chakrabarti, 2008; Draief, 2008). This threshold value is a
critical point in the system dynamics, and is not related to node
specific thresholds in the class of threshold models. We follow
this idea, adopt the Jacobian matrix of system (6) to evaluate
the local stability of the fixed point, and the result proved the
threshold of our model is 1.
Behavior of the Model on Small-World Network
We now investigate thl behavior for small-world
network topologies. Small-worl
e mode
d characteristics have been
w
in
testified in many real world networks and social networks. We
use the NW model (Newman, 1999) for generating the net-
orks. According to the algorithm, we generate a ring lattice,
where each node has K neighbors, K/2 in the clockwise, and
K/2 in the anticlockwise direction. Each edge is added with
probability , forbidding self-loops or multiple edges between
nodes. Additionally, all experiments start with one node in
status 1 and one in status 2, which can change their status as
time progresses. Moreover, in most of experiments rumor 1 and
2 are nearly equal, so as to observe their spread in the networks.
Figure 2 depicts the steady-state behavior of our model
when the rewiring parameter  is changed. The results are
shown for networks of two different sizes with the same clus-
tering coefficient of the initial ring lattice. The fraction of nodes
each status is given, as well as the fraction of nodes with
high degree in state j, (j = 1, 2, 3), normalized by


1jk, re-
spectively.
a
1
= 0.5, a
2
= 0.5
β = 0.3, γ = 0.4
N
= 100, K = 4
C(0) = 0.6327
s1
s2
s3
0.0001 0.001 0.01 0.1 1
probability 
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
proportion Ni
(a)
/N
a
1
= 0.5, a
2
= 0.5
β = 0.3, γ = 0.4
N
= 100, K = 4
C(0) = 0.6327
s1
s2
s3
0.0001 0.001 0.01 0.1 1
probability 
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
proportion Ni/N
(b)
Figure 2.
The final-state behavior of the model for different values of . Th
parameters include the fraction of nodes in each status and normaliz
clustering coefficient. (a) Results obtained from 100 nodes network
for each , run for k = 500 time units; (b) Results obtained
odes network realizations run for k = 1000 time units.
e
ed
realizations
from 1000 n
a
1
= 0.3, a
2
= 0.5
β = 0.2, γ = 0.8
N
= 1000, K = 10
C(0) = 0.6973
s1
s2
s3
0.0001 0.001 0.01 0.1 1
probability 
1
0.9
0.8
0.7
0.6
Ni/N
0.5
0.4
0.3
0.2
0.1
0
ro
pp
ortion
Figure 3.
The final-state behavior of the model for networks generated with the
NW small-world algorithm, using a starting ring lattice with 1000
nodes and K = 10.
tly, the results are the same due to the same level of
liquishness of the environment enables rumor
1
both of which are always preferred by a
given populatumors are
spreading throh every node
is
Eviden
clustering in the networks. Furthermore, for the particular val-
ues of the model parameters, status 1 and 2 also present a fixed
prportion. The co
to occupy a majority of high-degree nodes. However, as the
networks become increasingly random, status 2 expanded
mostly at the expense of status 1. The high degree clustering in
the small-world networks undermines the spreading of the ru-
mor 1.
Moreover, if the level of clustering in the networks is lower,
i.e., the cliquish neighborhoods are less, as in Figure 3, then
status 2 is the main remaining status, even if the parameters of
rumor 1 are much higher than those of rumor 2. The low clus-
tering of the networks acts to strengthen the influence of status 2.
In conclusion, few neighborhoods in a small-world network
disable the influence of the preferred rumor 1, and strengthen-
ing the spread of rumor 2. Rumor 1 is also easy to spread
through many long-range connections, quickly spreading the
rumor. While, Rumor 2 could only be the main status if a
small-world network does not have large highly connected
groups of nodes.
Conclusion and Discussion
In conclusion, we present a model of two rumors’ spread-
ing in this paper,
ion in a network. In this model, r
ugh small-world networks, in whic
classified into two kinds: high-degree and low-degree. And
each node has one of three potential states: 1, 2 and 3, corre-
sponding to supporter of rumor 1 or 2 and neutral. Our model
follows the idea of SIS model, and can be reduced to it when
some key parameters are changed. This model also has an
intrinsic propagating threshold 1 for rumor spreading,
where λ is the largest given value of adjacency matrix A, as
previous studies proved. There is also a unique stable fixed
point for our model, implying the choice of starting rumor 1
and 2 supporters.
We also present the preference of rumor 1 or 2 when the dis-
tribution degree of nodes is even enough and/or when the net-
work does not contain large clustered groups of nodes. This is
preformed in the model behavior on NW small-world network.
The number of nodes supporting rumor 1 and 2 is well ap-
proximated, which is similar in BA networks as the critical
degree m0 is increased.
480

Z. ZHU ET AL.
C
ang, Y., Wang, C., Leskovec, J., & Faloutsos, C.
thresholds in real networks. ACM Transactions on
Information and System Security, 10, 1-26.
doi:10.1145/1284680.
Acknowledgements
The work described in this paper was supported by the grant
(Grant No. 9024030) from the National Natural Science Foun-
dation of China.
REFERENCES
ane, V. R. (1966). A note on the size of epidemics and the number of
people hearing a rumour. J. R. Stat. Soc. Ser. B, 28, 487-490.
Chakrabarti, D., W
(2008). Epidemic
1284681
2005). Infection in sociaChristley, R. M. et al. (l networks: Using net-
work analysis to identify high-risk individuals. American Journal of
Epidemiology, 162, 1024-1031. doi:10.1093/aje/kwi308
Daley, D. J., & Kendall, D. G. (1964). Epidemics and rumours. Nature,
204, 1118. doi:10.1038/2041118a0
aley, D. J., & Kendall, D. G. (1965). Stochas
Applied Mathematics, 1, 42-55.
Dtic rumours. Journal of
doi:10.1093/imamat/1.1.42
Draief, M., Ganesh, A., & Massoulie, L. (2008). Thresholds for virus
spread on networks. Annals of Applied Probability, 18, 359-378.
doi:10.1214/07-AAP470
Goldenberg, J., Libai, B., Moldovan, S., & Muller, E. (2007). The NPV
of bad news. International Journal of Research in Marking, 24, 186-
200. doi:10.1016/j.ijresmar.2007.02.003
anovetter, M. (1978). Threshold models of collective bGr ehavior.
American Journal of Sociology, 83, 1420-1443. doi:10.1086/226707
G, Arenas, A., & Llas, M. uardiola, X., Diaz-Guilera, A., Perez, C. J.
(2002). Modeling diffusion of innovations in a social network.
Physical Review E, 66, Article ID: 026121.
doi:10.1103/PhysRevE.66.026121
empe, D., Kleinberg, J., & Tardos, E. (2003). Maximizing the spread
of influence in a social network. Proceed
SIGKDD International Conferenc
K
ing of the 9th ACM
e on Knowledge Discovery and
Data Mining (pp. 137-146). New York: ACM Press.
doi:10.1145/956750.956769
andahl, H. D. (1953). On the spread of information with time and
distance. Bulletin of Mathematical Biology, 15, 367-38
L
1.
doi:10.1007/BF02476410
Liu, Y. H. et al. (2011). Rumor riding: Anonymizing unstructured
peer-to-peer systems. IEEE Transactions on Parallel and
Systems, 22, 464-475.
Distributed
0.1109/TPDS.2010.98doi:1
Newman, M. J., Watts, D. J. (1999). Renormalization group analysis of
the small-world network model. Physics Letters A, 263, 341-346.
doi:10.1016/S0375-9601(99)00757-4
Rapoport, A., & Rebhun, L. I. (1952). On the mathematical theory of
rumor spread. Bulletin of Mathematical Biology, 14, 375-383.
doi:10.1007/BF02477853
Sudbury, A. (1985). The proportion of the population never hearing a
rumour. Journal of Applied Probability, 22, 443-446.
doi:10.2307/3213787
Trpevski, D. (2010). Model for rumor spreading over networks. Physi-
cal Review E, 81, Article ID: 056102.
doi:10.1103/PhysRevE.81.056102
016/0304-4149(87)90010-X
Watson, R. (1987). On the size of a rumour. Stochastic Processes and
Their Applications, 1, 141-149. doi:10.1