IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 5.2 Problem Solutions 5.2.1 Greedy Algorithm Based on the survival analysis,we propose an additive The proposed Greedy algorithm tries to block the rumor survival model where we assume that the probability of as fast as possible to prevent the rumor from further prop- node v getting activated is the weighted summation of agation.The working mechanism is as following:At time the propagation probabilities mentioned in(5)of all the to when we detect the rumor,we immediately select all K previously activated nodes set fu tu<t.Thus,in our nodes in our budget and block them (i.e.,remove all the context,the hazard rate is given by links of it so that it can not communicate with its neighbors). ao(tls(t))=aTs(t)=>auupav(t), Mathematically,the Greedy algorithm aims to minimize the (17 likelihood of inactive nodes getting activated at ti,i.e.,the u:tu<t next time stamp after the rumor is detected.The likelihood where ao=(auv),u =1,2,...,N is a non-negative pa- of nodes getting activated at time ti is given by rameter vector indicating the existence of the edge between node u and v.ouv=1 if there is an edge between them;and ftls(to》=Π QuvPuv(t1)X auv=0,otherwise. veVw2u:tu≤to We then define a coefficient matrix A:=[]ERNXN Ⅱeaeu房pen(rdrj (21) to denote the structure of the network in terms of the e:te≤to connection between any pair of nodes in the network.Let Ao be the original network coefficient matrix before any Correspondingly,the objective function is nodes are blocked.By substituting a(s(T))in (16)with minf(tls(to)】 (17),then we can have: (22) s.t.auw∈{0,1} F(ts(t))=1-e wPuu(r)dr Then,the greedy algorithm is presented as below: Algorithm 1 Greedy Algorithm =l-Ⅱeaue.mu(r)dr Input:Initial Edge matrix Ao. u:tu<t =l-e2…p()ir Initialization:VB =0. for i=1 to K do (18) u=argm[fts(to):A-i)-fts(to)片Ai-1l】 Accordingly,we have the likelihood function of the activa- Ai:=Ai-1\u, tion of node v,f(tls(t)),as following: VBVB Ufu). end for fu(ts(t))= dF(ts(t)) dt Output:VB. aupuu(t)I eaovfio Pou(dr .(19) u:tu<t e:te<t Given the activation likelihood of a single inactive node 5.2.2 Dynamic Blocking Algorithm v E VN2,now we consider any number of inactive nodes Different from the greedy blocking algorithm,which is a in a cascade,during the entire observation window T, type of static blocking algorithm,we propose a dynamic tsT=(t1,,t,,tNlto≤t≤to+T).We assume that rumor blocking algorithm aiming to incrementally block the every activation is conditionally independent on activations selected nodes instead of blocking them at once.In that case, occurring later given previous activations.Then we can the blocking strategy is split into several rounds and each compute the activation likelihood as: round can be regarded as a greedy algorithm.Thus,how to choose the number of rounds is also very important for the f(t≤T;A)=Π∑QuvPuv(t)× algorithm.In the following part,we will elaborate on the al- i:ti<Tu:tu<ti gorithm design and how we choose the specific parameters. Ⅱeooe i pes(rdrj (20) From the probabilistic perspective,we seek to formulate the likelihood of inactive nodes becoming activated in every p:te<ti round of rumor blocking.Correspondingly,the likelihood Based on the activation likelihood function,we then function is given by design the blocking algorithms.First,we choose to select and block all K nodes at the same time to.As is shown f6ls(，传-》=Π∑auPa传)与× in Eq.(20),the activation likelihood of an inactive node veV(t与)utu<t) v is related to the hazard rate coming from all previously activated nodes.Therefore,the early activated nodes play Ⅱeoeed Pew(rdrj (23) a significant role in the entire process.Hence,we propose e:te<tj the following greedy algorithm to minimize the influence where V(t;)represents the set of nodes which remain of the rumor within one time stamp after it is detected.We inactive at time stamp tj. assume that there are M time steps:t1,...,tM during the Different from the case of greedy algorithm,the objective whole observation window T,with each time step lasting function of the dynamic blocking algorithm is implemented T/M. in several rounds.In each round,it is similar to equation (22).We assume that there are n rounds of blocking inIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 7 5.2 Problem Solutions Based on the survival analysis, we propose an additive survival model where we assume that the probability of node v getting activated is the weighted summation of the propagation probabilities mentioned in (5) of all the previously activated nodes set {u : tu < t}. Thus, in our context, the hazard rate is given by αv(t|s(t)) = α T v s(t) = X u:tu<t αuvpuv(t), (17) where αv = (αuv), u = 1, 2, . . . , N is a non-negative pa￾rameter vector indicating the existence of the edge between node u and v. αuv = 1 if there is an edge between them; and αuv = 0, otherwise. We then define a coefficient matrix A := [αv] ∈ R N×N + to denote the structure of the network in terms of the connection between any pair of nodes in the network. Let A0 be the original network coefficient matrix before any nodes are blocked. By substituting αv(τ |s(τ )) in (16) with (17), then we can have: Fv(t|s(t)) =1 − e − R t tu P u:tu<t αuvpuv(τ)dτ =1 − e − P u:tu<t R t tu αuvpuv(τ)dτ =1 − Y u:tu<t e −αuv R t tu puv(τ)dτ =1 − e − P u:tu<t αuv R t tu puv(τ)dτ (18) Accordingly, we have the likelihood function of the activa￾tion of node v, fv(t|s(t)), as following: fv(t|s(t)) =dFv(t|s(t)) dt = X u:tu<t αuvpuv(t) Y %:t%<t e −α%v R t t% p%v(τ)dτ . (19) Given the activation likelihood of a single inactive node v ∈ VN2 , now we consider any number of inactive nodes in a cascade, during the entire observation window T, t ≤T = (t1, . . . , ti , . . . , tN |t0 ≤ ti ≤ t0 + T). We assume that every activation is conditionally independent on activations occurring later given previous activations. Then we can compute the activation likelihood as: f(t ≤T ; A) = Y i:ti<T X u:tu<ti αuvpuv(ti)× Y %:t%<ti e −α%v R ti t% p%v(τ)dτ . (20) Based on the activation likelihood function, we then design the blocking algorithms. First, we choose to select and block all K nodes at the same time t0. As is shown in Eq. (20), the activation likelihood of an inactive node v is related to the hazard rate coming from all previously activated nodes. Therefore, the early activated nodes play a significant role in the entire process. Hence, we propose the following greedy algorithm to minimize the influence of the rumor within one time stamp after it is detected. We assume that there are M time steps: t1, . . . , tM during the whole observation window T, with each time step lasting T /M. 5.2.1 Greedy Algorithm The proposed Greedy algorithm tries to block the rumor as fast as possible to prevent the rumor from further prop￾agation. The working mechanism is as following: At time t0 when we detect the rumor, we immediately select all K nodes in our budget and block them (i.e., remove all the links of it so that it can not communicate with its neighbors). Mathematically, the Greedy algorithm aims to minimize the likelihood of inactive nodes getting activated at t1, i.e., the next time stamp after the rumor is detected. The likelihood of nodes getting activated at time t1 is given by f(t1|s(t0)) = Y v∈VN2 X u:tu≤t0 αuvpuv(t1)× Y %:t%≤t0 e −α%v R t1 t% p%v(τ)dτ . (21) Correspondingly, the objective function is min A f(t1|s(t0)) s. t. αuv ∈ {0, 1}. (22) Then, the greedy algorithm is presented as below: Algorithm 1 Greedy Algorithm Input: Initial Edge matrix A0. Initialization: VB = ∅. for i = 1 to K do u = arg max v∈V [f(t1|s(t0); Ai−1) − f(t1|s(t0); Ai−1\v)] Ai := Ai−1\u, VB = VB ∪ {u}. end for Output: VB. 5.2.2 Dynamic Blocking Algorithm Different from the greedy blocking algorithm, which is a type of static blocking algorithm, we propose a dynamic rumor blocking algorithm aiming to incrementally block the selected nodes instead of blocking them at once. In that case, the blocking strategy is split into several rounds and each round can be regarded as a greedy algorithm. Thus, how to choose the number of rounds is also very important for the algorithm. In the following part, we will elaborate on the al￾gorithm design and how we choose the specific parameters. From the probabilistic perspective, we seek to formulate the likelihood of inactive nodes becoming activated in every round of rumor blocking. Correspondingly, the likelihood function is given by f(tj |s(tj−1)) = Y v∈V (tj ) X u:tu<tj αuvpuv(tj )× Y %:t%<tj e −α%v R tj t% p%v(τ)dτ , (23) where V (tj ) represents the set of nodes which remain inactive at time stamp tj . Different from the case of greedy algorithm, the objective function of the dynamic blocking algorithm is implemented in several rounds. In each round, it is similar to equation (22). We assume that there are n rounds of blocking in