## 5 Our Proposed Algorithm for BCIM Problem
### Lower and Upper Bound Functions
#### 5.1.2 Lower Bound Submodular Function  
We next devise a lower submodular function of objective function. The idea of this method is that we only choose set of nodes that make \(v\) becomes \(A\)-active with probability \(1\) in estimating of objective function. We consider set \(C_{L}(g,v)\) defined as follows:  
\[C_{L}(g,v)=\{u|d_{A}(u,v)<\tau,d_{A}(u,w)<d_{B}(S_{B},w),\forall w\in\mathsf{P} _{A}(u,v)\} \tag{17}\]  
where \(\mathsf{P}_{A}(u,v)\) is the simple path from \(u\) to \(v\) in \(g_{A}\). The left inequality in Equation (17) ensures that \(v\) can reach from \(u\) on \(g_{A}\). The right inequality ensures the influence from \(u\) to \(v\) is not blocked by the influence from \(S_{B}\). Consider the example in Figure 5. We have the sample graph \(g\) that contains nine nodes and eight edges, the source nodes is \(v\) and \(S_{B}=\{c,h\}\) and \(\tau=5\). \(g_{A}\) contains edges: \((a,v),(b,a),(c,b),(d,b)\). \(g_{B}\) contains edges: \((f,v),(e,f),(h,e),(i,e)\). We have \(C_{L}(g,v)=\{b,a,v\}\). According CLE model, we can easily prove that \(\gamma_{g}^{v}(u)=1,\forall u\in C_{L}(g,v)\). Based on that, we define _Lower bound Reachable Reversal_ (LRR) set as follows:  
**Definition 4**. : LRR _set. Given graph \(G=(V,E,w_{A},w_{B})\), a random LRR set \(R_{j}\) is generated from \(G\) by: (1) picking a random node \(v\in V\); and (2) generating a sample graph \(g\) from \(G\) by_ CLE _model and returning \(R_{j}\gets C_{L}(g,v)\)._  
For any \(S_{A}\subset V\setminus S_{B}\), denote a random variable:  
\[Y_{j}= \begin{cases}1,\text{ If }R_{j}\cap S_{A}\
eq\emptyset\\ 0,\text{ Otherwise}\end{cases}  \tag{18}\]  
and define \(\mathbb{L}(S)=n_{0}\cdot\mathbb{E}[Y_{j}]\). Let \(\mathcal{R}\) be a set of LRR. We estimate \(\mathbb{L}(S)\) as  
\[\hat{\mathbb{L}}(S_{A})=\frac{n_{0}}{|\mathcal{R}|}\sum_{R_{j}\in\mathcal{R}} Y_{j} \tag{19}\]  
Lemma 4 shows the properties of \(\mathbb{L}\) function. **Lemma 4**. : _Given seed set \(S_{B}\), for any set of nodes \(S_{A}\subseteq V\setminus S_{B}\), we have: \(\mathbb{L}(S_{A})\leq\mathbb{I}(S_{A})\) and \(\mathbb{L}(\cdot)\) is a monotone and submodular function._  
The proof of Lemma 4 is omitted here because it is similar to that of Lemma 3. Based on Lemma 4, we use \(\mathbb{L}\) as a lower-bound submodular function of \(\mathbb{I}\). Algorithm 1 depicts the generation of LRR set. We first randomly select source node \(v\), and then select an edge \((u,v)\) on \(g_{A}\) according to the Competitive live-edge model. If edge \((u,v)\) is selected, we update \(d_{A}\) as the distance from \(u\) to \(v\) on \(g_{A}\) and check distance condition \(d_{A}(u,v)<d_{B}(u,S_{B})\) by Algorithm 2. In this algorithm, we sequentially generate a simple path from \(u\) on \(g_{B}\) (called \(B\)-path) according to the CLE model until the length of path exceeds \(d_{A}\), or no \(B\)-edge is selected. If \(d_{B}\leq d_{A}\) (Lines 13-16, Algorithm 2), it returns _True_ and Algorithm 1 returns current LRR set \(R_{j}\) (Line 14, Algorithm 1). In Algorithm 1, if node \(u\) is selected into \(R_{j}\), it moves from \(v\) to \(u\) and repeats process until distance from current selected node to \(v\) on \(g_{A}\) exceeds \(\tau\) (Line 18, Algorithm 1), or no \(A\)-edge is selected (Line 16, Algorithm 1). This process ensures that, if node \(u\) is added to the set \(R_{j}\), the previous nodes on \(P_{A}(u,v)\) are not affected by \(S_{B}\). Figure 5: Description for \(C_{L}(g,v)\).