IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 4.3 Objective Formulation 5.1.1 Survival Function Now our goal is to minimize the influence of a rumor as In order to analyze the likelihood of nodes getting activated much as possible (e.g.minimize the number of activated during one time slot in a cascade,we adopt the Survival nodes at the end of propagation process)under the con- Theory to calculate the probability of a single node v getting straint of user experience utility.We formulate the DRIMUX activated in a given time period.First,we introduce the problem as follows: survival function defined as [46] min [∑s(T] S(t)=Pr(t<T), (11) U∈V (10) where T is a continuous random variable representing the s.t.Uhom(Uhet)>Uth, occurrence time of an event of interest,t is a specified where s(T)represents the state of a node v by end of a constant.The survival function represents the probabili- ty that the event of interest occurs after the observation time intervalT as denoted in Equation(6).E[s(T)] "deadline".If we use the terminology "death"to represent denotes the expected number of activated nodes by the the occurrence of the event,we can claim that the target end of T.The constraint condition restrains the user expe- rience above a threshold Uth.In the following section we "survives"if its occurrence takes place after the specified time t.Then we have the cumulative distribution function will discuss how the user experience constraint affects the F(t): activation likelihood of each node. F(t)=Pr(T≤t)=1-S(t) (12) Accordingly,the probability density function f(t)is given PROPOSED SOLUTIONS by In this section,we analyze the DRIMUX optimization prob- f(t)=d lem from the perspective of a network inference problem F=-S. (13) with survival theory and then propose the greedy algorithm Alternatively,there is another method named hazard and dynamic blocking algorithm based on different nodes rate to express the instant activation rate of node v.Specif- selection schemes and the maximum likelihood principle. ically,the hazard rate indicates the probability of a single node with current state s(t)getting activated at time (t+dt). 5.1 Survival Theory We define (ts(t))as the hazard rate of node v condi- tioned on the set of nodes activated by time t.Our goal now In this section,we analyze the likelihood of nodes getting is to analyze the impact of the hazard rate of different nodes activated during each time slot in the process of rumor to the rumor influence minimization problem. propagation using the Survival Theory.Firstly,in our model, we assume that a rumor has been spreading for some time 5.1.2 Hazard Rate before it is detected at time to.Specifically,we assume Based on the above analysis,the hazard rate can be viewed that when the ratio of the infected nodes reaches a certain threshold,it would draw the attention of the monitoring as an alternative interpretation of the distribution of T, which characterizes the instantaneous rate of occurrence of department and then be detected whether it is a rumor or an event.It is defined as: not.If it is a rumor,relevant blocking strategies would be initiated to block it.Mathematically,we use I(t)to denote a(ts(t))=lim Pr(t≤T≤t+dtT>t) the ratio of infected nodes in the social network at time t. dt-0 dt It is also assumed that by time to,there have already been a total number of N1 activated nodes,and N2 lim Pr(t≤T≤t+dt) dt-0 Pr(T>t)dt N-Ni nodes remain inactive.Let VN,and VN2 denote the F(t+dt)-F(t) set of activated and inactive nodes at time to respectively. lim dt-0 S(t)dt Therefore,from to on,the system can be viewed as N 1 independent cascades propagating through the network, lim F(t+dt)-F(t) and our goal is to select K nodes from N2 and block them S(t)t→0 dt so that the final number of activated nodes during the =- S'() (14) observation time window T can be minimized. S(t) S(t) LetC=(c1,...,cN)denote the set of cascades triggered by Ni activated nodes by time to.A cascade ci C where S'(t)is the derivative of S(t).Pr(t T<t+dtT> can be represented by a N-dimensional time vector t= t)denotes the conditional probability that the event of (t,...,t),where tE [to,to+T]uoo},j=1,2,...,N2 interest will occur in time period [t,t+dt)given that it has is the activated time of node j in cascade ci.The observation not occurred before time t. time window T is decided by the user experience utility Accordingly,we can have constraint mentioned in(10),and oo means the node is not S(t)=e-oa(rls())dr (15) activated until the end of the observation time (to +T). Here,we first consider the propagation process of only one and for a certain node v,according to (12),we have cascade and then the results can be extended to the scenario of multiple cascades. Fu(ts(t))=1-e-(rls())dr (16)IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 6 4.3 Objective Formulation Now our goal is to minimize the influence of a rumor as much as possible (e.g. minimize the number of activated nodes at the end of propagation process) under the con￾straint of user experience utility. We formulate the DRIMUX problem as follows: min E[ X v∈V sv(T) ] s. t. Uhom(Uhet) ≥ Uth, (10) where sv(T) represents the state of a node v by end of a time interval T as denoted in Equation (6). E[ P v∈V sv(T) ] denotes the expected number of activated nodes by the end of T. The constraint condition restrains the user expe￾rience above a threshold Uth. In the following section we will discuss how the user experience constraint affects the activation likelihood of each node. 5 PROPOSED SOLUTIONS In this section, we analyze the DRIMUX optimization prob￾lem from the perspective of a network inference problem with survival theory and then propose the greedy algorithm and dynamic blocking algorithm based on different nodes selection schemes and the maximum likelihood principle. 5.1 Survival Theory In this section, we analyze the likelihood of nodes getting activated during each time slot in the process of rumor propagation using the Survival Theory. Firstly, in our model, we assume that a rumor has been spreading for some time before it is detected at time t0. Specifically, we assume that when the ratio of the infected nodes reaches a certain threshold, it would draw the attention of the monitoring department and then be detected whether it is a rumor or not. If it is a rumor, relevant blocking strategies would be initiated to block it. Mathematically, we use I(t) to denote the ratio of infected nodes in the social network at time t. It is also assumed that by time t0, there have already been a total number of N1 activated nodes, and N2 = N − N1 nodes remain inactive. Let VN1 and VN2 denote the set of activated and inactive nodes at time t0 respectively. Therefore, from t0 on, the system can be viewed as N1 independent cascades propagating through the network, and our goal is to select K nodes from N2 and block them so that the final number of activated nodes during the observation time window T can be minimized. Let C = (c1, . . . , cN1 ) denote the set of cascades triggered by N1 activated nodes by time t0. A cascade ci ∈ C can be represented by a N-dimensional time vector t ci = (t ci 1 , . . . , tci N2 ), where t ci j ∈ [t0, t0+T]∪{∞}, j = 1, 2, . . . , N2 is the activated time of node j in cascade ci . The observation time window T is decided by the user experience utility constraint mentioned in (10), and ∞ means the node is not activated until the end of the observation time (t0 + T). Here, we first consider the propagation process of only one cascade and then the results can be extended to the scenario of multiple cascades. 5.1.1 Survival Function In order to analyze the likelihood of nodes getting activated during one time slot in a cascade, we adopt the Survival Theory to calculate the probability of a single node v getting activated in a given time period. First, we introduce the survival function defined as [46] S(t) = P r(t < T), (11) where T is a continuous random variable representing the occurrence time of an event of interest, t is a specified constant. The survival function represents the probabili￾ty that the event of interest occurs after the observation “deadline”. If we use the terminology “death” to represent the occurrence of the event, we can claim that the target “survives” if its occurrence takes place after the specified time t. Then we have the cumulative distribution function F(t): F(t) = P r(T ≤ t) = 1 − S(t). (12) Accordingly, the probability density function f(t) is given by f(t) = d dtF(t) = −S 0 (t). (13) Alternatively, there is another method named hazard rate to express the instant activation rate of node v. Specif￾ically, the hazard rate indicates the probability of a single node with current state s(t) getting activated at time (t+dt). We define αv(t|s(t)) as the hazard rate of node v condi￾tioned on the set of nodes activated by time t. Our goal now is to analyze the impact of the hazard rate of different nodes to the rumor influence minimization problem. 5.1.2 Hazard Rate Based on the above analysis, the hazard rate can be viewed as an alternative interpretation of the distribution of T, which characterizes the instantaneous rate of occurrence of an event. It is defined as: αv(t|s(t)) = lim dt→0 P r(t ≤ T ≤ t + dt|T > t) dt = lim dt→0 P r(t ≤ T ≤ t + dt) P r(T > t)dt = lim dt→0 F(t + dt) − F(t) S(t)dt = 1 S(t) lim dt→0 F(t + dt) − F(t) dt = f(t) S(t) = − S 0 (t) S(t) , (14) where S 0 (t) is the derivative of S(t). P r(t ≤ T ≤ t+dt|T > t) denotes the conditional probability that the event of interest will occur in time period [t, t+dt) given that it has not occurred before time t. Accordingly, we can have S(t) = e − R t 0 αv(τ|s(τ))dτ , (15) and for a certain node v, according to (12),we have Fv(t|s(t)) = 1 − e − R t 0 αv(τ|s(τ))dτ . (16)