IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING scription of the concept of ferromagnetism in Physics [42]. 4 PROBLEM FORMULATION Specifically,it describes the phenomenon that when an array of atomic spins align in the way that the magnetic moments 4.1 Dynamic Rumor Propagation with Ising Model associated to them will all point in the same direction. Kempe et al.[14]considered the success probability puv Then it will create a macroscopic magnetic moment.Gen- as a system parameter and is fixed at the very beginning erally speaking,the Ising model contains two parts-the of the cascade.However,based on the topic dynamics we microscopic and macroscopic parts.The microscopic part discussed in a previous section,at different time steps of represents the local or individual behavior which is the the propagation process,a topic can vary dramatically in alignment of each of the atomic spins.Correspondingly,its popularity.Besides,the rumor attraction [27]for each the macroscopic part stands for the global or collective individual node u E V is also a realistic factor we should behavior which is the exterior magnetic moment.Based on take into account.That means the success of rumor prop- its intrinsic attributes,the Ising model can be generalized to agation between neighbors includes two aspects:first,the other similar scenarios.In our work,we utilize it to model activated node u has to be so attracted by the rumor that the rumor propagation process in social networks. it will choose to send the rumor to its neighbors;second, one of u's inactive neighbors v decides to accept the rumor Only after those two steps,we can claim that v is activated. In other words,the success of rumor propagation depends 3.4 User Experience both on the global popularity and the individual tendency of the rumor topic,which can be regarded as a generalized User experience is an important factor for various services feature of the Ising model. including social networks [43].Existing rumor blocking strategies block either nodes (users)or links (connections Now we investigate the two steps of a successful rumor propagation.In the first step,at any time stamp ti,u is between users)in social networks to prevent the rumor from further propagation.However,none has analyzed the one of the activated nodes in time stamp tj-1.Based on the work in [27],we give the modified version of the probability impact of blocking nodes.Generally speaking,the longer the user is blocked,the less satisfactory the user feels about of node u sending the rumor to one of its inactive neighbors vas the social network.Therefore,if the blocked time surpasses Po a certain threshold,it is possible that the user may quit pd(与）=1g(10+t) (1) the social network or at least lodge a complaint to the administrator.Bhatti et al.[44]analyzed the user-perceived where po is the initial sending probability at time stamp 0. quality in web server design and found that users'tolerance On the receiving end,the probability of node v accepting for latency decreases over the duration of interaction with the rumor transmitted by its parent node u is also given as a site.A utility function was presented to measure the piuce =1/Dv, (2) customer satisfaction.Inspired by that,in our work,we apply a modified utility function to measure user experience where D is the in-degree of node v.That denotation can in rumor blocking. be interpreted as that if a node has very high degree,it will receive more information than those with lower degrees.In that case,due to the large number of pieces of information 3.5 Rumor Influence Minimization it receives,every single piece of information will have much lower possibility to be read,recognized and forwarded by Rumor influence minimization addresses the problem of the node.For example,if a user has only one friend on minimizing the propagation effect of undesirable rumors a social network,he or she would probably read all the in social networks.Figure 3 demonstrates the mechanism messages forwarded by his or her friend,and thus if the user of rumor blocking in social networks.It shows both the finds a rumor interesting,he or she will probably believe normal rumor propagation process without any blockage in and forward it.In contrast,if a user has hundreds or even the social network and the process blocking a set of nodes thousands of friends,he or she could easily miss most of the on the path of rumor propagation.The rumor influence information. minimization problem is converse to the classic influence Thus,based on the above analysis,we then give the maximization problem [14]. probability of successful rumor propagation from u to v as It has been investigated in different influence diffusion mod- els in social networks.Fan et al.[20]studied the least cost rumor blocking problem in social networks,and introduced aat,）=pd,哈=D。g10+t 1 Po (3) the notion of "protectors"to limit the bad influence of ru- which can be defined as the individual tendency between mors by initiating a protector cascade to propagate against different pair of nodes in the network. the rumor cascade.Greedy algorithm is proposed for both Now we discuss the global topic popularity of the ru- opportunistic and deterministic cascade models.However, mor.As mentioned in related work,the rumor popularity Kimura et al.[19]proposed the strategy of blocking links generally includes three phases and approximately subject instead of nodes in social networks so as to minimize the to the chi square distribution,which is given by propagation of malicious rumors.Different contamination minimization problems are defined based on different defi- 21-)tk-1e-号 nitions of contamination degree of a network. Pglb(t;k)= T() (4)IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 4 scription of the concept of ferromagnetism in Physics [42]. Specifically, it describes the phenomenon that when an array of atomic spins align in the way that the magnetic moments associated to them will all point in the same direction. Then it will create a macroscopic magnetic moment. Gen￾erally speaking, the Ising model contains two parts – the microscopic and macroscopic parts. The microscopic part represents the local or individual behavior which is the alignment of each of the atomic spins. Correspondingly, the macroscopic part stands for the global or collective behavior which is the exterior magnetic moment. Based on its intrinsic attributes, the Ising model can be generalized to other similar scenarios. In our work, we utilize it to model the rumor propagation process in social networks. 3.4 User Experience User experience is an important factor for various services including social networks [43]. Existing rumor blocking strategies block either nodes (users) or links (connections between users) in social networks to prevent the rumor from further propagation. However, none has analyzed the impact of blocking nodes. Generally speaking, the longer the user is blocked, the less satisfactory the user feels about the social network. Therefore, if the blocked time surpasses a certain threshold, it is possible that the user may quit the social network or at least lodge a complaint to the administrator. Bhatti et al. [44] analyzed the user-perceived quality in web server design and found that users’ tolerance for latency decreases over the duration of interaction with a site. A utility function was presented to measure the customer satisfaction. Inspired by that, in our work, we apply a modified utility function to measure user experience in rumor blocking. 3.5 Rumor Influence Minimization Rumor influence minimization addresses the problem of minimizing the propagation effect of undesirable rumors in social networks. Figure 3 demonstrates the mechanism of rumor blocking in social networks. It shows both the normal rumor propagation process without any blockage in the social network and the process blocking a set of nodes on the path of rumor propagation. The rumor influence minimization problem is converse to the classic influence maximization problem [14]. It has been investigated in different influence diffusion mod￾els in social networks. Fan et al. [20] studied the least cost rumor blocking problem in social networks, and introduced the notion of “protectors” to limit the bad influence of ru￾mors by initiating a protector cascade to propagate against the rumor cascade. Greedy algorithm is proposed for both opportunistic and deterministic cascade models. However, Kimura et al. [19] proposed the strategy of blocking links instead of nodes in social networks so as to minimize the propagation of malicious rumors. Different contamination minimization problems are defined based on different defi- nitions of contamination degree of a network. 4 PROBLEM FORMULATION 4.1 Dynamic Rumor Propagation with Ising Model Kempe et al. [14] considered the success probability puv as a system parameter and is fixed at the very beginning of the cascade. However, based on the topic dynamics we discussed in a previous section, at different time steps of the propagation process, a topic can vary dramatically in its popularity. Besides, the rumor attraction [27] for each individual node u ∈ V is also a realistic factor we should take into account. That means the success of rumor prop￾agation between neighbors includes two aspects: first, the activated node u has to be so attracted by the rumor that it will choose to send the rumor to its neighbors; second, one of u’s inactive neighbors v decides to accept the rumor. Only after those two steps, we can claim that v is activated. In other words, the success of rumor propagation depends both on the global popularity and the individual tendency of the rumor topic, which can be regarded as a generalized feature of the Ising model. Now we investigate the two steps of a successful rumor propagation. In the first step, at any time stamp tj , u is one of the activated nodes in time stamp tj−1. Based on the work in [27], we give the modified version of the probability of node u sending the rumor to one of its inactive neighbors v as p send u (tj ) = p0 lg(10 + tj ) , (1) where p0 is the initial sending probability at time stamp 0. On the receiving end, the probability of node v accepting the rumor transmitted by its parent node u is also given as p acc v = 1/Dv, (2) where Dv is the in-degree of node v. That denotation can be interpreted as that if a node has very high degree, it will receive more information than those with lower degrees. In that case, due to the large number of pieces of information it receives, every single piece of information will have much lower possibility to be read, recognized and forwarded by the node. For example, if a user has only one friend on a social network, he or she would probably read all the messages forwarded by his or her friend, and thus if the user finds a rumor interesting, he or she will probably believe and forward it. In contrast, if a user has hundreds or even thousands of friends, he or she could easily miss most of the information. Thus, based on the above analysis, we then give the probability of successful rumor propagation from u to v as pind(tj ) = p send u · p acc v = 1 Dv p0 lg(10 + tj ) , (3) which can be defined as the individual tendency between different pair of nodes in the network. Now we discuss the global topic popularity of the ru￾mor. As mentioned in related work, the rumor popularity generally includes three phases and approximately subject to the chi square distribution, which is given by pglb(t; k) = 2 (1− k 2 ) t k−1 e − t 2 2 Γ( k 2 ) , (4)