## 4 Models and Problem Definition  
### Time Constraint Competitive Linear Threshold (\(\mathsf{TCLT}\)) Model  
In this section, we introduce our model incorporating \(\mathsf{CLT}\) model with limited spread step \(\tau\), namely Time Constraint Competitive Linear Threshold Model (\(\mathsf{TCLT}\)). In addition, we propose a new tie-breaking rule in our model that can truly reflect the competitive context in viral marketing by our explanation.  
In this model, we reuse all notations and symbols in \(\mathsf{CLT}\) model. Given a constraint of propagation hop \(\tau\geq 1\), the propagation process happens in discrete steps \(t=0,1,\ldots,\tau\) as follows:  
* At step \(t=0\), \(A_{0}=S_{A},B_{0}=S_{B}\).
* At step \(t\geq 1\), first set \(A_{t}=A_{t-1}\) and \(B_{t}=B_{t-1}\). Each node \(v\
otin A_{t-1}\cup B_{t-1}\) becomes \(A\)-active if \[\begin{cases}\sum_{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)\geq\theta_{A}(v)\\ \sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)<\theta_{B}(v)\end{cases}\] (4) Node \(v\) becomes \(B\)-active if \[\begin{cases}\sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)\geq\theta_{B}(v)\\ \sum_{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)<\theta_{A}(v)\end{cases}\] (5)
* If in step \(t\), a node \(v\) has \[\begin{cases}\sum_{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)\geq\theta_{A}(v)\\ \sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)\geq\theta_{B}(v)\end{cases}\] (6)We propose _weight proportional probability tie-breaking rule_ (TB-WPP) to determine its state. Accordingly, \(v\) is \(A\)-activated with probability.  
\[p_{A}(v|A_{t-1},B_{t-1})=\frac{\sum_{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)}{\sum _{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)+\sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)}\]  
and \(v\) is \(B\)-activated with probability  
\[p_{B}(v|A_{t-1},B_{t-1})=\frac{\sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)}{\sum _{u\in N_{-}(v)\cap A_{t-1}}w_{A}(u,v)+\sum_{u\in N_{-}(v)\cap B_{t-1}}w_{B}(u,v)}\]  
* Once a node becomes activated (\(A\)-active or \(B\)-active), it keeps this status in the next steps. The propagation process ends after \(\tau\) hops of propagation or no more nodes can be activated.  
Different from TB-PP, in TB-WPP rule, we consider the total influence weight of the in-neighbors to decide state of node \(v\). Our TB-WPP rule reflects more closely the competition process. Consider the example in Figure 1 to clarify this observation. Graph \(G\) contains four nodes \(\{a,b,c,u\}\) and three edges \(\{(a,u),(b,u),(c,u)\}\). There is a pair \((w_{A},w_{B})\) on each edge, \(S_{A}=\{a,b\},S_{B}=\{c\}\). At step \(t=1\), if we use TB-PP, node \(v\) will change its state from inactive to \(A\)-active or \(B\)-active with probabilities \(\frac{2}{3}\) and \(\frac{1}{3}\), respectively. In other words, the probability \(v\) becomes \(A\)-active is higher. If we use TB-WPP, node \(v\) would change its state to inactive to \(A\)-active or \(B\)-active with probabilities \(\frac{3}{\Pi}\) and \(\frac{8}{\Pi}\), i.e. probability \(v\) becomes \(B\)-active is higher. In this case, the influence weight of \(c\) (0.8) for \(u\) is greater than that of two nodes \(a,b\) (total influence weight is 0.3). Considering the total weigh in TB-WPP rule is more suitable for the fact that users create different influences on each other depending on the relationship between them. Therefore, it is reasonable to consider TB-WPP about the competitive influence spread.