IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 5 where >0 represents the degree of freedom,I()is the propagation process. Gamma function.It explains a common social phenomenon Heterogeneous Networks.In heterogeneous social net- that when a rumor spreads for a while,it may create a works,different nodes have distinct properties.For exam- "rumor atmosphere"that could affect the judgements or ple,in real world social networks like Twitter or Weibo, decisions of users on online social networks. different users have different levels according to the time According to the Ising model [28],the"phase transition" they have spent on it,the number of followers they have of a spin involves both short-range interaction with its or the number of messages they have posted.Typically, nearest neighbors and long-term system evolution,and is we can simply divide all users into VIPs and ordinary a combined result.Inspired by that,we propose the co- users considering their levels.Intuitively,the social network operative propagation probability integrating Palb(t;k)with operators would try to avoid blocking the VIP users as Pind(t)in the form of a logistic function as possible as they can because of the impact they have on 1 the enormous followers and hence on the entire network. Pu(d=1+exp-B'psbt内+Pm可 On the other hand,from the perspective of the VIPs,since they usually have frequent interactions with their followers, 1 there is a high possibility that they can not tolerate to be 1+exp- B,--竖+六品可 blocked for a long time.As a result,the VIPs usually have a T() relatively low tolerance threshold of the blocked time. (5) Let C(u)denote the level of node u,and T(u)denote the where B1,B2 E(0,1)are the balance coefficients which tolerance threshold of node u when it is blocked.Then we satisfy B1+B2=1. propose the following expression: Based on this cooperative propagation probability,the 1 probability of node v getting activated at time stamp t;can T(u=c(西 (8) be given by The mechanism can be explained as follows.When the level Pr[s(G)=1刂=1-Π[1-su(G-)pun(tl, (6) of a user u,C(u),is approximate to zero,i.e.,the user has UEP just joined the social network,its tolerance threshold is close where Pr]represents probability,and P represents the to infinity,because even if it is blocked forever,it can just parent nodes of v. apply for a new account without any loss.On the contrary, if u is a VIP user,the higher its level is,the less blocked time it can endure.When C(u)is large enough,its tolerance will 4.2 User Experience Utility be asymptotic to zero. In the formulated optimization problem,one important There are several metrics to define the level or sig- constraint condition is the user experience utility function.nificance of a node in a social network,such as degree, Therefore,before giving the concrete algorithm,first,we eigenvector or betweenness.Also there is a widely adopt- elaborate on the user experience utility function. ed PageRank algorithm [45]which can be regarded as a It is a common sense that user experience is a critical variant of eigenvector centrality.For simplicity,we here use element in the success of modern business.A large variety the degree of a node u,D(u),to represent its level,i.e., of communication services involve user experience,such as C(u)=D(u),where is a constant coefficient.Thus,the web searching,telephone connecting,et.al.For customers user experience utility in a heterogeneous network can be using those services,the latency plays a tremendous role written as in their satisfaction extent,i.e.,the user experience utility. N Specifically,in our proposed problem,the user experience 11 >(1-SD(u)T6(u) (9) utility lies in the blocked time t of the selected node u. N In our work,we try to find the proper user experience utility function to characterize the impact of nodes being Given the user experience utility,now we analyze the blocked to the entire social network.Specifically,we analyze strategy of blocking nodes of different levels and its influ- both the homogeneous and heterogeneous scenarios. ence to the entire network.Our goal now is to select a certain Homogeneous Networks.For homogeneous social net- number of nodes and then block them so that the final active works,the simple case,we assume that all the nodes have nodes within a duration can be minimized.Nevertheless,it the same blocked time threshold Tih.In other words,we is a challenge to select the proper nodes to block without assume that all the users in the same social network have triggering the complaint of users.Let's assume that every same tolerance of the time being blocked regardless of the time a node is blocked longer than its tolerance threshold, time they have been in the social network.In this scenario, it will trigger a complaint to the operator.Besides,we also based on the user experience definition on web server in assume that a fraction of its neighbors will also trigger a [44],we define the user experience utility function as certain amount of complaints.For example,some users may attract many followers by frequently sharing interesting 1 information,so if they are blocked for a long time,and the Uhom N Th-To(u) N (7 followers fail to receive the information,it is likely that some u=l of them may lodge a complaint.In the following part,we where the Tih represents the tolerance time threshold,T(u)will use survival theory to analyze the process mentioned is used to record the blocked time of node u in the whole above.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 5 where k > 0 represents the degree of freedom, Γ(·) is the Gamma function. It explains a common social phenomenon that when a rumor spreads for a while, it may create a “rumor atmosphere” that could affect the judgements or decisions of users on online social networks. According to the Ising model [28], the “phase transition” of a spin involves both short-range interaction with its nearest neighbors and long-term system evolution, and is a combined result. Inspired by that, we propose the co￾operative propagation probability integrating pglb(t; k) with pind(t) in the form of a logistic function as puv(t) = 1 1 + exp − β1 · pglb(t; k) + β2 · pind(t) = 1 1 + exp −  β1 2 (1− k 2 ) t k−1e − t2 2 Γ( k 2 ) + β2 1 Dv p0 lg(10+t) , (5) where β1, β2 ∈ (0, 1) are the balance coefficients which satisfy β1 + β2 = 1. Based on this cooperative propagation probability, the probability of node v getting activated at time stamp tj can be given by P r[sv(tj ) = 1] = 1 − Y u∈Pv [1 − su(tj−1)puv(tj )], (6) where P r[·] represents probability, and Pv represents the parent nodes of v. 4.2 User Experience Utility In the formulated optimization problem, one important constraint condition is the user experience utility function. Therefore, before giving the concrete algorithm, first, we elaborate on the user experience utility function. It is a common sense that user experience is a critical element in the success of modern business. A large variety of communication services involve user experience, such as web searching, telephone connecting, et.al. For customers using those services, the latency plays a tremendous role in their satisfaction extent, i.e., the user experience utility. Specifically, in our proposed problem, the user experience utility lies in the blocked time t b u of the selected node u. In our work, we try to find the proper user experience utility function to characterize the impact of nodes being blocked to the entire social network. Specifically, we analyze both the homogeneous and heterogeneous scenarios. Homogeneous Networks. For homogeneous social net￾works, the simple case, we assume that all the nodes have the same blocked time threshold Tth. In other words, we assume that all the users in the same social network have same tolerance of the time being blocked regardless of the time they have been in the social network. In this scenario, based on the user experience definition on web server in [44], we define the user experience utility function as Uhom = 1 N X N u=1 Tth − Tb(u) Tth , (7) where the Tth represents the tolerance time threshold, Tb(u) is used to record the blocked time of node u in the whole propagation process. Heterogeneous Networks. In heterogeneous social net￾works, different nodes have distinct properties. For exam￾ple, in real world social networks like Twitter or Weibo, different users have different levels according to the time they have spent on it, the number of followers they have or the number of messages they have posted. Typically, we can simply divide all users into VIPs and ordinary users considering their levels. Intuitively, the social network operators would try to avoid blocking the VIP users as possible as they can because of the impact they have on the enormous followers and hence on the entire network. On the other hand, from the perspective of the VIPs, since they usually have frequent interactions with their followers, there is a high possibility that they can not tolerate to be blocked for a long time. As a result, the VIPs usually have a relatively low tolerance threshold of the blocked time. Let L(u) denote the level of node u, and T (u) denote the tolerance threshold of node u when it is blocked. Then we propose the following expression: T (u) = 1 L(u) . (8) The mechanism can be explained as follows. When the level of a user u, L(u), is approximate to zero, i.e., the user has just joined the social network, its tolerance threshold is close to infinity, because even if it is blocked forever, it can just apply for a new account without any loss. On the contrary, if u is a VIP user, the higher its level is, the less blocked time it can endure. When L(u) is large enough, its tolerance will be asymptotic to zero. There are several metrics to define the level or sig￾nificance of a node in a social network, such as degree, eigenvector or betweenness. Also there is a widely adopt￾ed PageRank algorithm [45] which can be regarded as a variant of eigenvector centrality. For simplicity, we here use the degree of a node u, D(u), to represent its level, i.e., L(u) = ζD(u), where ζ is a constant coefficient. Thus, the user experience utility in a heterogeneous network can be written as Uhet = 1 N X N u=1 (1 − ζD(u)Tb(u)). (9) Given the user experience utility, now we analyze the strategy of blocking nodes of different levels and its influ￾ence to the entire network. Our goal now is to select a certain number of nodes and then block them so that the final active nodes within a duration can be minimized. Nevertheless, it is a challenge to select the proper nodes to block without triggering the complaint of users. Let’s assume that every time a node is blocked longer than its tolerance threshold, it will trigger a complaint to the operator. Besides, we also assume that a fraction of its neighbors will also trigger a certain amount of complaints. For example, some users may attract many followers by frequently sharing interesting information, so if they are blocked for a long time, and the followers fail to receive the information, it is likely that some of them may lodge a complaint. In the following part, we will use survival theory to analyze the process mentioned above.