# Influence Maximization with Priority in Online Social Networks
## 4 Sampling Algorithm with Provable Guarantees
### Algorithm Description and Theoretical Analysis
Generate set of \(N_{1}\) RR samples \(\mathcal{R}_{2}\)
12 repeat
13\(t\gets t_{0}\), \(i\gets 0\)
14 while\(i<t\)do
15\(u\leftarrow\arg\max_{v\in V\setminus S_{2}}\left(\hat{\sigma}(S_{2}\cup\{v\})- \hat{\sigma}(S_{2})\right)\)
16 if\(u\in S_{1}\)then
17\(t\gets t+1\)
18 end if
19\(S_{2}\gets S_{2}\cup\{u\}\), \(i\gets i+1\)
20 end if
21 Calculate \(F_{I}(S_{2},\mathcal{R}_{2},\delta_{2})\) and \(F_{u}(S_{2},\mathcal{R}_{2},\delta_{2})\)
22 if\(\frac{F_{I}(S_{2},\mathcal{R}_{2},\delta_{2})}{F_{u}(S_{2},\mathcal{R}_{2}, \delta_{2})}\geq 1-(1-\frac{1}{k})^{t}-\epsilon\)then
23 return\(S_{2}\)
24 else
25 Generate \(|\mathcal{R}_{2}|\) RR samples and add them into \(\mathcal{R}_{2}\)
26 end if
27 until\(|\mathcal{R}_{2}|\geq N_{max}\);
28\(S\gets S_{1}\cup S_{2}\)
29 return\(S\);
```  
**Algorithm 3**Integrated Greedy -based Sampling (IGS) algorithm Theoretical analysis.Fortunately, the sequence of random variables \(X_{g}(S)\) and \(Y_{g}(S)\) constructed from the RR and TRR samples can be shown to form a martingale. For any random variable \(X_{g}(S)\in[0,1]\), let a random variable \(M_{i}=\sum_{j=1}^{i}(X_{g}^{i}(S)-\mu),\forall i\geq 1\), where \(\mu=\mathbb{E}[X_{g}]\). For a sequence of random variables \(M_{1},M_{2},\ldots\) we have \(\mathbb{E}[M_{i}|M_{1},\ldots,M_{j-1}]=\mathbb{E}[M_{i-1}]+\mathbb{E}[X_{g}^{ i}(S)-\mu]=\mathbb{E}[M_{i-1}]\). Hence, \(M_{1},M_{2},\ldots\) be a form of martingale [41]. Similarly, \(Y_{g}\) is also a form of martingale. Therefore, the following concentration inequality [41] applies:  
**Lemma 3**. : _If \(M_{1},M_{2},\ldots\) be a form of martingale, \(|M_{1}|\leq a\), \(|M_{j}-M_{j-1}|\leq a\) for \(j\in[1,i]\), and_  
\[\mathsf{Var}[M_{1}]+\sum_{j=2}^{i}\mathsf{Var}[M_{j}|M_{1},M_{2},\ldots,M_{j-1 }]=b \tag{22}\]  
_where \(\mathsf{Var}[\cdot]\) denotes the variance of a random variable. Then, for any \(\lambda\), we have:_  
\[\Pr[M_{i}-\mathbb{E}[M_{i}]\geq\lambda]\leq\exp\left(-\frac{\lambda^{2}}{ \frac{2}{3}a\lambda+2b}\right) \tag{23}\]  
Apply this Lemma with \(|M_{1}|=|X_{g}^{1}(S)|\leq 1\), \(|M_{j}-M_{j-1}|=|X_{g}^{j}(S)-X_{g}^{j-1}(S)|\leq 1\), \(\mathsf{Var}[M_{1}]=\mathsf{Var}[X_{g}^{1}(S)-\mu]=\mathsf{Var}[X_{g}(S)]\), \(\mathsf{Var}[M_{j}|M_{1},M_{2},\ldots,M_{j-1}]=\mathsf{Var}[X_{g}^{j}(S)-\mu]= \mathsf{Var}[X_{g}(S)]\), and \(\mathsf{Var}[X_{g}(S)]\leq\mu(1-\mu)\leq\mu\), we have:  
\[\Pr\Big{[}\sum_{i=1}^{|\mathcal{R}|}X_{g}^{i}(S)-|\mathcal{R}|\cdot\mu\geq \lambda\Big{]}\leq\exp\left(-\frac{\lambda^{2}}{\frac{2}{3}\lambda+2\mu| \mathcal{R}|}\right) \tag{24}\]  
Similarly, \(-M_{1},\ldots,-M_{i},\ldots\) also form a Martingale, so apply Lemma 3, we have:  
\[Pr\Big{[}\sum_{i=1}^{|\mathcal{R}|}X_{g}^{i}(S)-|\mathcal{R}|\cdot\mu\leq- \lambda\Big{]}\leq\exp\left(-\frac{\lambda^{2}}{2\mu|\mathcal{R}|}\right) \tag{25}\]  
Let \(\lambda=\epsilon\mu|\mathcal{R}|\) and put it in two above inequalities, we have:  
\[\Pr[\sum_{i=1}^{|\mathcal{R}|}X_{g}^{i}-|\mathcal{R}|\cdot\mu\geq \epsilon|\mathcal{R}|\mu]\leq\exp\left(-\frac{\epsilon^{2}|\mathcal{R}|\mu}{2 +\frac{2}{3}\epsilon}\right) \tag{26}\] \[\Pr[\sum_{i=1}^{|\mathcal{R}|}X_{g}^{i}-|\mathcal{R}|\cdot\mu\leq -\epsilon|\mathcal{R}|\mu]\leq\exp\left(-\frac{\epsilon^{2}|\mathcal{R}|\mu}{2 }\right) \tag{27}\]  
The following Lemma shows the lower-bound of the influence of candidate solution \(S_{1}\). **Lemma 4**. : _The candidate solution \(S_{1}\) obtained by phase 1 of Algorithm 3 satisfies \(\Pr[\sigma_{U}(S_{1})\geq T]\geq 1-\delta\)_  
Solve the above quadratic inequality for \(\mu\), we obtain upper-bound for \(\mu\) is,  
\[\mu \leq\max\left\{\hat{\mu},\hat{\mu}+\frac{1}{N_{t}}\left(\sqrt{c^{2}+2 N_{t}c\hat{\mu}}-c\right)\right\} \tag{46}\] \[=\hat{\mu}+\frac{1}{N_{t}}\left(\sqrt{c^{2}+2N_{t}c\hat{\mu}}-c\right) \tag{47}\]  
Denote \(S^{0}=\arg\max_{S,|S|\leq k}\hat{\sigma}(S)\), where \(\hat{\sigma}\) is calculated over \(\mathcal{R}_{t}^{2}\). Since the phase of Algorithm 3 selects a candidate solution \(S_{2}^{t}\) by a greedy strategy.