Sociology Mind 2012. Vol.2, No.4, 477481 Published Online October 2012 in SciRes (http://www.SciRP.org/journal/sm) http://dx.doi.org/10.4236/sm.2012.24061 Copyright © 2012 SciRes. 477 Rumor Spreading and DegreeRelated Preference Mechanism on a SmallWorld Network* Zhi Zhu, Fengjian Liu, Dongsheng Liao Humanities and Social Sciences School, National University of Defense Technology, Changsha, China Email: kdbybs@126.com Received July 3rd, 2012; revised August 6th, 2012; accepted August 19th, 2012 An alternate model for rumor spreading over smallworld 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, highdegree nodes always consider rumor 1 first, and lowdegree nodes always consider rumor 2 first. The model is a natural generalization of the wellknown epidemic SIS model and reduces to it when some of the parameters of this model are zero. We find that rumor 1 (preferred by highdegree 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 smallworld model a moderate level of clustering supports its adoption, while increasing randomness reduces it. Keywords: Rumor; DegreeRelated Preference Mechanism; SmallWorld Network Introduction Rumor spreading is a complex sociopsychological 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 DaleyKendall 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 cohypothesis 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 smallworld 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 wom 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 wom on a firm’s profits. In this study, negative wom 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 SmallWorld Network we describe the behavior of the model on NW smallworld 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 multiagent 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 smallworld 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 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 substates, which denote the degree of nodes. Suppose 1j i k or 2j i k (j = 1, 2, 3) be the status vector of node i, signifying it is a highdegree or lowdegree node in state j. The state of node i becomes 11112 , iii ksksk , 22122 , iii ksksk , 33132 , iii ksksk , i.e., 12 , jjj iii 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 kd , di = 1 if degre ei ≥ m0, otherwise, di = 0. The critical degree m0, distinguishing the highdegree nodes from lowdegree 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 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 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 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 ks k , 2 1 11 N ii j jj 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 degreerelated 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 highdegree 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 lowdegree 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 realworld 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 Copyright © 2012 SciRes. 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 wordofmouth 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 ks k , 2 1 N i i Yks k and 3 12 1 N i i 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 ks k , 2 2 1 N j ji i ks k, (j = 1, 2, 3), respectively. Suppose 1 NEX , , and 2 NEY 33132 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 ka pk jj 2 1 11 N ii j kap k (5) 31 3 i i k k k 11 i 12 i 1 i s 21 i 22 i 2 i s 31 i 32 i 3 i s 1 a 1 1a 2 a 2 1a i (1 ) ii f i (1 ) ii g Figure 1. The model of rumor spreading with degreerelated 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 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 kxkykgfaxk yk (6) xkykfgayk and jj 1 11 N ii j ka xk jj 2 1 11 N ii j kay k (7) 31 3 i i k k 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 Copyright © 2012 SciRes. 479
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 SmallWorld Network We now investigate thl behavior for smallworld network topologies. Smallworl 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 selfloops 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 steadystate 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 = 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 = 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 finalstate 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 = 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 ortion Figure 3. The finalstate behavior of the model for networks generated with the NW smallworld 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 highdegree nodes. However, as the networks become increasingly random, status 2 expanded mostly at the expense of status 1. The high degree clustering in the smallworld 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 smallworld 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 longrange connections, quickly spreading the rumor. While, Rumor 2 could only be the main status if a smallworld 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 smallworld networks, in whic classified into two kinds: highdegree and lowdegree. 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 smallworld 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. Copyright © 2012 SciRes. 480
Z. ZHU ET AL. Copyright © 2012 SciRes. 481 C ang, Y., Wang, C., Leskovec, J., & Faloutsos, C. thresholds in real networks. ACM Transactions on Information and System Security, 10, 126. 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, 487490. Chakrabarti, D., W (2008). Epidemic 1284681 2005). Infection in sociaChristley, R. M. et al. (l networks: Using net work analysis to identify highrisk individuals. American Journal of Epidemiology, 162, 10241031. 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, 4255. 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, 359378. doi:10.1214/07AAP470 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, 14201443. doi:10.1086/226707 G, Arenas, A., & Llas, M. uardiola, X., DiazGuilera, 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. 137146). 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, 36738 L 1. doi:10.1007/BF02476410 Liu, Y. H. et al. (2011). Rumor riding: Anonymizing unstructured peertopeer systems. IEEE Transactions on Parallel and Systems, 22, 464475. Distributed 0.1109/TPDS.2010.98doi:1 Newman, M. J., Watts, D. J. (1999). Renormalization group analysis of the smallworld network model. Physics Letters A, 263, 341346. doi:10.1016/S03759601(99)007574 Rapoport, A., & Rebhun, L. I. (1952). On the mathematical theory of rumor spread. Bulletin of Mathematical Biology, 14, 375383. doi:10.1007/BF02477853 Sudbury, A. (1985). The proportion of the population never hearing a rumour. Journal of Applied Probability, 22, 443446. 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/03044149(87)90010X Watson, R. (1987). On the size of a rumour. Stochastic Processes and Their Applications, 1, 141149. doi:10.1
