# Influence Maximization with Priority in Online Social Networks
## 4 Sampling Algorithm with Provable Guarantees
### Estimator of Influence Functions  
Firstly, we recap the concept of _Reachable Reverse (RR)_ set [40] to estimate influence function \(\sigma(\cdot)\). Base on that, we propose the concept of _Targeted Reachable Reverse (TRR)_ set to estimate influence function \(\sigma_{U}(S)\). Then we propose IGS algorithm and provide theoretical analysis based on statistical evidence. **Definition 2** (Reachable Reverse (RR) set [40]). : _Given a graph \(G=(V,E)\) under IC model. A random RR set \(R_{j}\) is generated from \(G\) by:_  
1. _Picking a source node_ \(u\) _with probability_ \(\frac{1}{n}\)_._
2. _Generating a sample graph_ \(g\) _from_ \(G\)_, and returning_ \(R_{j}\) _as nodes which can be reached from_ \(u\) _in_ \(g\)_._  
For a random RR set \(R_{j}\), define a random variable \(X_{g}(S)=\min\{1,|R_{g}\cap S|\}\). [PERSON] et al. [40] show that RR samples can be used to estimate the influence function by applying the following Lemma. **Lemma 1**. : _For any set of nodes \(S\subseteq V\), we have \(\sigma(S)=n\cdot\mathbb{E}[X_{g}(S)]\)._  
Given a set of RR set \(\mathcal{R}\), and a set node \(S\), we can approximate the value of \(\sigma(S)\) by \(\hat{\sigma}(S)\) defined as follow:  
\[\hat{\sigma}(S)=\frac{n}{|\mathcal{R}|}\sum_{R_{S}\in\mathcal{R}}X_{g}(S) \tag{20}\]  
Generating RR sets can be accomplished by using IM algorithms in [13; 14; 15; 20; 23]. The common algorithm for generating RR set \(R_{j}\) is described in Algorithm 2. This algorithm first selects a source node \(u\) with a probability \(\frac{1}{n}\) to add into \(R_{j}\). The algorithm uses a queue \(Q\) to store the visited nodes. Initially, \(u\) is also added to \(Q\). The algorithm next retrieves each node \(v\) in \(Q\) and picks an incoming node \(x\) with probability \(p(x,v)\) (line 6). If successful, it adds \(x\) in to \(Q\) and \(R_{j}\). This process takes place until the set \(Q\) is empty. ```
Input: Graph \(G=(V,E)\) under IC model Output: A RR Sample \(R_{j}\)
1. Pick a source node \(u\) with probability \(\frac{1}{n}\)
2. Initialize a queue \(Q=\{u\}\) and \(R_{j}=u\)
3.while\(Q\) is not emptydo
4.\(v\gets Q.pop()\)
5 foreach\(x\in N_{in}(v)\setminus(R_{j}\cup Q)\)do
6. With probability \(p(x,v)\): \(Q.push(x)\) and \(R_{j}\gets R_{j}\cup\{u\}\)
7. end while
8.end
```  
**Algorithm 2**Generating RR sample under IC model  
We now introduce the definition of _Targeted Reachable Reverse (TRR)_ Set on the basis of modifying RR concept. **Definition 3** (Targeted Reachable Reverse (TRR) Set). : _Given a graph \(G=(V,E)\) under \(\mathsf{IC}\) model. A random TRR set \(R_{j}^{U}\) is generated from \(G\) by:_  
1. _Picking a source node_ \(u\in U\) _with probability_ \(\frac{1}{|U|}\)_._
2. _Generating a sample graph_ \(g\) _from_ \(G\)_, and returning_ \(R_{g}^{U}\) _as nodes which can be reached from_ \(u\) _in_ \(g\)_._  
We define a random variable \(Y_{g}(A)=\min\{1,|R_{g}^{U}\cap S|\}\). Similar to Lemma 1, Lemma 2 shows that we can use the value of \(Y_{g}(S)\) to estimate function \(\sigma_{U}(S)\). **Lemma 2**. : _For any set of nodes \(S\subseteq V\), we have \(\sigma_{U}(S)=|U|\cdot\mathbb{E}[Y_{g}(S)]\)_  
Proof. : Denote \(R_{g}^{U}(u)\) is a TRR sample with a source node \(u\) for the sample graph \(g\), we have:  
\[\sigma_{U}(S) =\sum_{g\sim G}|R(g,S\to U)|\] \[=\sum_{u\in U}\sum_{g\sim G}\Pr[g\sim G][\exists v\in S:u\text{ is reached from }v]\] \[=\sum_{u\in U}\sum_{g\sim G}\Pr[g\sim G][\exists v\in S:v\in R _{g}^{U}(u)]\] \[=|U|\sum_{u\in V}\frac{1}{|U|}\sum_{g\sim G}\Pr[g\sim G]Y_{g}(S)\] \[=|U|\sum_{u\in V}\sum_{g\sim G}\Pr[u\text{ is source node}]\Pr[g \sim G]Y_{g}(S)\] \[=|U|\cdot\mathbb{E}[Y_{g}(S)]\]  
The transition from the second equality to the third equality comes from the definition of \(R_{g}^{U}(u)\) and from the third to the fourth then to the fifth is caused by the distribution of choosing a node \(u\) as a source node.