## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
For Wiki network, which has 1.79 millions nodes and 28.5 millions edges, our algorithm finished in 90 s.

Figure 8: Running time of algorithms for BCIM problem. #### 6.2.4 Impact of \(\tau\)

Considering the importance of early competitive influence in viral marketing, we were very interested in the role of time constraint in influence. We compared our solution with three other algorithms while varying \(\tau\) from 3 to 5. Figure 9 shows results of algorithms when \(L=50\). SPBA was clearly still the best performer. Specifically, our SPBA was 1.01-1.23 times better than BCT and up to 2.5 times better than Degree. ## 7 Conclusions

In this paper, we investigate BCIM problem, which finds the seed set of a player to maximize their influence while their competitors are conducting similar strategies. We first propose TCLT model to capture the competitive influence of two competitors on a social network and formulate BCIM in this model. We provide the hardness results and properties of objective function. A randomized SPBA-based approximation is proposed for finding the solution of BCIM. Experiments on real world social networks were conducted. The results show that our proposed algorithm outperformed the other heuristics. Investigation, C.V.P. and H.V.D. ; Methodology, C.V.P. ; Supervision, H.X.H. and M.T.T. This research received no external funding. The authors declare no conflict of interest. ## Appendix A

Proof of Theorem 3.: We use the inductive method according to two models when \(t=0,1,2...,\tau\). In the step \(t=0\), we have \(A_{0}=A_{0}^{\prime}\) and \(B_{0}=B_{0}^{\prime}\). Assume that, at step \(t\geq 0\), the two models give the same distribution of \(A\)-active set and \(B\)-active set nodes, which are \(A_{t}\) and \(B_{t}\). For TCLT model, we consider a node \(v\) that has not been activated by the end of step \(t\), i.e., \(v\
otin A_{t}\cup B_{t}\). We divide the state of \(v\) in step \(t+1\) into two cases:

Figure 9: Comparison between different algorithms when \(\tau\) varies. Cases 1: Total \(A\)-influence weights exceed threshold \(\theta_{A}(v)\) while the total \(B\)-influence weights is smaller than \(\theta_{B}(v)\) in step \(t+1\). The probability that this case happens is:

\[P_{1,t+1}(v)=\frac{\big{(}\sum_{u\in A_{t}\setminus A_{t-1}}w_{A}(u,v)\big{)} \big{(}1-\sum_{u\in B_{t}\setminus B_{t-1}}w_{B}(u,v)\big{)}}{\big{(}1-\sum_{u \in A_{t-1}}w_{A}(u,v)\big{)}\big{(}1-\sum_{u\in B_{t-1}}w_{B}(u,v)\big{)}} \tag{11}\]

Cases 2: Total \(A\)-influence weights exceed threshold \(\theta_{A}(v)\) while the total negative influence weights also exceed than threshold \(\theta_{B}(v)\). The probability that this case happens is:

\[P_{2,t+1}(v)=\frac{\big{(}\sum_{u\in A_{t}\setminus A_{t-1}}w_{A}(u,v)\big{)} \big{(}\sum_{u\in B_{t}\setminus B_{t-1}}w_{B}(u,v)\big{)}}{\big{(}1-\sum_{u \in A_{t-1}}w_{A}(u,v)\big{)}\big{(}1-\sum_{u\in B_{t-1}}w_{B}(u,v)\big{)}} \tag{12}\]

In this case, TB-WPP rule is used to determine state of \(v\). According to this rule, the probability node \(v\) is \(A\)-activated at step \(t+1\) is equal to

\[P_{1,t+1}(v)+p_{A}(v|A_{t-1},B_{t-1})\cdot P_{2,t}(v) \tag{13}\]

On CLE model, we assume that \(A_{t}^{\prime}\) and \(B_{t}^{\prime}\) are the set of \(A\)-active set and \(B\)-active set nodes at step \(t\). For \(v\
otin B_{t}^{\prime}\cup A_{t}^{\prime}\), the probability that \(v\) has an in-edge from \(A_{t}^{\prime}\) and does not have an in-edge from \(B_{t}^{\prime}\) (called \(P_{1,t}^{\prime}(v)\)) is equal to

\[P_{1,t}^{\prime}(v)=\frac{\big{(}\sum_{u\in A_{t}^{\prime}\setminus A_{t-1}^{ \prime}}w_{A}(u,v)\big{)}\big{(}1-\sum_{u\in B_{t}\setminus B_{t-1}^{\prime}} w_{B}(u,v)\big{)}}{\big{(}1-\sum_{u\in A_{t-1}^{\prime}}w_{A}(u,v)\big{)}\big{(}1- \sum_{u\in B_{t-1}^{\prime}}w_{B}(u,v)\big{)}}=P_{1,t}(v) \tag{14}\]

We denote \(P_{2,t}^{\prime}(v)\) as the probability \(v\) has both in-edge from \(A_{t}^{\prime}\) and in-edge from \(B_{t}^{\prime}\).