## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
* Degree: This algorithm selects nodes with the highest degree and we keep on adding the highest-degree nodes until total costs of the selection of nodes exceeds \(L\). * Random: This algorithm randomly selects nodes within budget \(L\). #### 6.1.3 Parameters

In all the experiments, we kept \(\epsilon=0.1\) and \(\delta=1/n\) as general settings. We set \(\epsilon^{\prime}=\delta^{\prime}=0.01\) and used the stopping condition algorithm in [35] to estimate \(\hat{\mathbb{I}}\). We assigned the weights of edges in TCLT model according to LT model in previous studies [4; 5; 6; 7; 8; 13]. The weight of the edge \((u,v)\) was calculated as follows,

\[w(u,v)=\frac{1}{|N_{-}(v)|} \tag{38}\]

Our implementation was written in C++ and compiled with GCC 4.7. All our experiments were carried out using a Linux machine with a 2 \(\times\) Intel(R) Xeon(R) CPU E5-2697 v4 @ 2.30 GHz 8 \(\times\) 16 GB DIMM ECC DDR4 @ 2400 MHz

### Results

#### 6.2.1 Comparison of Algorithms under General Case

In this experiment, we compared algorithms when \(\tau=5\), the budget \(L\) varied from 0 to 100 and the costs of node were uniformly distributed in \([1.0,3.0]\). Figure 6 shows the performance of all algorithms on Gnutella, Enron, Epinions, Email-Eu, DBLP and Wiki networks. On average, we observed that our algorithm SPBA always had the best performance. SPBA was 10-30% better than the result of BCT. This is because BCT only considers the number of influenced nodes and ignores the competitive influence under time constraint \(\tau\). It also confirmed that IM's algorithms do not have good performance for BCIM problem. Random algorithm had the worst performance of all cases. Degree algorithm performed well on the Enron dataset but had bad performance on the other datasets. SPBA was up to 7.7 times better than Degree. The reason is that Degree only uses the topology properties of the social network but can not consider competitive diffusion process. In the opposite, our algorithm takes advantage of the upper and lower bounds of objective function to obtain the approximation ratio. This explains why our algorithm had good performance while the others had poor performance in many cases. #### 6.2.2 Comparison of Algorithms under Unit-Cost Setting

To show more clearly the performance of these algorithms, we conducted experiments on the unit-cost case (i.e., all node costs are equal to 1) on Gnutella, Enron, Epinions and Email-EU datasets. We set \(\tau=5\) and \(L\) varied from 1 to 100. Figure 7 displays the results of all algorithms. Once again, we found that our algorithm SPBA gave the best performance. SPBA was 1.06-1.76 times better than BCT and 1.2-17.2 times better than the result of Degree. These results are also consistent with what was observed in the previous case. Figure 6: Comparison between different algorithms under general cost setting. Figure 7: Comparison between different algorithms under unit-cost setting. #### 6.2.3 Comparison of Running Time

Figure 8 shows running time of algorithms on six datasets. SPBA had the longest running time on any datasets. This is because the running time of SPBA consists of total running time of \(\mathsf{PBA}(\mathbb{L},G,L,\epsilon,\delta)\), \(\mathsf{PBA}(\mathbb{U},G,L,\epsilon,\delta)\) and calculating \(\hat{\mathbb{L}}(\cdot)\). Random and Degree algorithms are simple heuristic algorithms thus their costs are low. This resulted in their shortest running time. Although \(\mathsf{BCT}\) is based on polling method, it ran faster than our algorithm. The reason for this result is due to the following reasons. Firstly, the sampling process of \(\mathsf{BCT}\) and our algorithm are different. The sampling complexity of \(\mathsf{BCT}\) is mainly dependent on the number of randomly selected node while the sampling process in our algorithm is more complicated because it must check the influence paths from \(S_{B}\). Secondly, to obtain a data approximation, our algorithm must solve three problems with polling based method. It is worth noting that SPBA is scalable with million-scale networks.