## 5 Our Proposed Algorithm for BCIM Problem
### Lower and Upper Bound Functions
#### 5.1.1 Upper Bound Function  
For a random source node \(v\) and a sample graph \(g\) with given \(B\)-seed set \(S_{B}\), the idea of this method is that we only choose set of nodes satisfying: (1) the distance of influence path from them to \(v\) is smaller than \(\tau\); and (2) the influence path from them to \(v\) is not blocked by \(S_{B}\). We consider set \(C_{U}(g,v)\) defined as follows:  
\[C_{U}(g,v)=\{u|d_{A}(u,v)\leq\tau,d_{A}(u,v)<d_{B}(u,S_{B})\} \tag{13}\]  
Figure 4 shows an example of \(C(g,v)\). In this example, the sample graph \(g\) contains nine nodes and eight edges, the source nodes is \(v\) and \(S_{B}=\{c,h\}\) and \(\tau=4\). \(g_{A}\) contains edges: \((a,v),(b,a),(c,b),(d,h)\). \(g_{B}\) contains edges: \((f,v),(e,f),(f,e),(h,f)\). We have \(C_{U}(g,v)=\{b,a,v\}\). Node \(d\) lies on the simple path that ends at \(v\), but it cannot influence \(v\) since its influence is blocked by \(c\). We define _Upper bound Reachable Reversal_ (URR) set as follows:  
**Definition 3** (URR set). : _Given graph \(G=(V,E,w_{A},w_{B})\), a random URR set \(R_{j}\) is generated from \(G\) by: (1) picking a random source node \(v\in V\); and (2) generating a sample graph \(g\) from \(G\) by running CLE model, and returning \(R_{j}\leftarrow C_{U}(g,v)\)._  
Figure 3: Framework of SPBA algorithm. For any \(S_{A}\subseteq V\setminus S_{B}\), denote a random variable:  
\[X_{j}= \begin{cases}1,\text{ If }R_{j}\cap S_{A}\
eq\emptyset\\ 0,\text{ Otherwise}\end{cases}  \tag{14}\]  
We denote \(R_{j}(g,v)\) is a URR set with source node \(v\) and sample graph \(g\), and \(X_{j}(g,v)\) is value of \(X_{j}\) corresponding to \(R_{j}(g,u)\). The following lemma shows the upper bound characters of \(X_{j}\). **Lemma 2**. : _For any set \(S_{A}\subseteq V\setminus S_{B}\), a random source node \(v\) and random sample graph \(g\), we have \(X_{j}(g,v)\geq\gamma_{g}^{v}(S_{A})\)._  
Proof. : We consider two following cases  
Case 1: \(S_{A}\cap R_{j}(g,v)=\emptyset\), each node \(u\in S_{A}\) cannot reach \(v\) in \(g_{A}\) after \(\tau\) steps. By running CLE model, \(S_{A}\) cannot activate \(v\). Hence, \(X_{j}(g,v)=\gamma_{g}^{v}(S_{A})=0\). Case 2: \(S_{A}\cap R_{j}(g,v)\
eq\emptyset\). Assume that \(u\in S\cap R_{j}(g,v)\), \(u\) can reach \(v\) in \(g_{A}\) after \(\tau\) steps, thus \(\mathbb{E}[\gamma_{g}^{v}(S_{A})]\leq 1=X_{j}(g,v)\). Therefore, \(\gamma_{g}^{v}(S_{A})\leq X_{j}(g,v)\). Define \(\mathbb{U}(S_{A})=n_{0}\cdot\mathbb{E}[X_{j}]\) and \(\mathcal{R}\) is a set of URR. We estimate \(\mathbb{U}(S_{A})\) as  
\[\mathbb{U}(S_{A})=\frac{n_{0}}{|\mathcal{R}|}\sum_{R_{j}\in\mathcal{R}}X_{j} \tag{15}\]  
Lemma 3 shows the properties of \(\mathbb{U}\) function. **Lemma 3**. : _Given seed set \(S_{B}\subset V\), for any set of nodes \(S_{A}\subseteq V\setminus S_{B}\), we have: \(\mathbb{U}(S_{A})\geq\mathbb{I}(S)\) and \(\mathbb{U}(\cdot)\) is a monotone and submodular function._  
Proof. : Using Lemma 2, we have  
\[ \begin{array}{ll}\mathbb{I}(A)&=n_{0}\cdot\sum_{g\in X_{G}}\Pr[g|G]\sum_{v \in V\setminus S_{B}}\gamma_{g}^{v}(A)\\ &\leq n_{0}\cdot\sum_{g\in X_{G}}\Pr[g|G]\sum_{v\in V\setminus S_{B}}X_{j}(g, v)=\mathbb{U}(A)\end{array}  \tag{16}\]  
Since \(\mathbb{U}(S)=n_{0}\cdot\mathbb{E}[X_{j}]=n_{0}\cdot\sum_{X_{j}}\Pr[X_{j}] \mathbb{E}(S\cap R_{j}\
eq\emptyset)\) is a form of _weight coverage_ function, in which every \(R_{j}\) is an element, the universal is set of all URR sets, and each node \(u\in V\) corresponding to a subsets that contains LRR \(R_{j}\) is covered by \(u\). The probability \(n_{0}\Pr[g|G]\) is the weight of element \(R_{j}^{g}(u)\). Since the weighted coverage function is monotone and submodular, it follows that \(\mathbb{U}(A)\) has the same properties  
Lemma 3 suggests that we can use \(\mathbb{U}\) as an upper bound submodular function of \(\mathbb{I}\). We further devise an algorithm, which is summarized in Algorithm 1, to generate an URR set. We first randomly  
Figure 4: Description for \(C_{U}(g,v)\).