# Influence Maximization with Priority in Online Social Networks
## 4 Sampling Algorithm with Provable Guarantees
### Algorithm Description and Theoretical Analysis  
_Algorithm description_. The algorithm is detailed in Algorithm 3. It generates the set of \(N_{U}\) TRR sets \(\mathcal{R}_{1}\), and set two candidate solutions \(S_{1}\), \(S_{2}\) empty at first. Then the body of the algorithm divides into two phases. In phase 1, it finds a candidate solution \(S_{1}\) with minimum-size so that \(\hat{\sigma}(S)\geq(1+\alpha)T\) by using a greedy strategy with potential function \(\hat{\sigma}\) over \(\mathcal{R}_{1}\). In each iterator, it selects a node \(u\) with maximal incremental value of the potential function (line 4) until \(\hat{\sigma}(S)\geq(1+\alpha)T\). The candidate solution \(S_{1}\) obtained by this phase satisfies the priority constraint, \(\sigma_{U}(S_{1})\geq T\) with probability at least \(1-\delta\) (Lemma 4). The phase 2 selects a candidate solution \(S_{2}\) with the remaining budget (\(t=k-|S_{1}|\)) so that the influence spread \(\sigma(\cdot)\) is maximized. In this phase, it first sets the parameters \(\epsilon_{1},t_{max}\), \(N_{max}\) and generates \(N_{1}\) set of RR samples \(\mathcal{R}_{2}\). The main of this phase operates in several iterators (line 12-27)until meeting the stopping condition (line 22). In each iterator, it finds a candidate solution \(S_{2}\) by a greedy strategy. It picks a node \(u\) with maximal incremental of approximation influence \(\hat{\sigma}(\cdot)\) over \(\mathcal{R}_{2}\) (line 12) until \(t\) nodes are selected. Similar to IG algorithm, if \(u\) already belongs to \(S_{1}\), the algorithm increases \(t\) by 1. After that, the algorithm checks the quality of candidate solution \(S_{2}\) (line 17). It calculates \(F_{I}(S_{2},\mathcal{R}_{2},\delta)\)- a lower-bounded of \(\sigma(S_{2})\), and \(F_{u}(S_{2},\mathcal{R}_{2},\delta)\)-an upper-bounded of an optimal solution respect to IMP problem. These functions ensure the statistical criterion, which are claimed in the Lemmas 5 and 6. If solution \(S_{2}\) meets the approximation condition (line 19), the algorithm returns \(S_{2}\). If not, it moves to the next iterator and stops when the number of TRR samples is at least \(N_{max}\) (line 21). ```
Input: Graph \(G=(V,E)\), \(U\subset V,k\), \(T,\epsilon,\alpha,\delta\in(0,1)\) Output: Seed set \(S\)
1. Generate a set of \(N_{U}=(2+\frac{2}{3}\alpha)|U|\frac{\ln((||U|/2)^{1/\delta})}{(T+T\alpha) \alpha^{2}}\) TRIS sets \(\mathcal{R}_{1}\). 2.\(S_{1}\leftarrow\emptyset,S_{2}\leftarrow\emptyset\) /* Phase 1 */
3 while\(\hat{\sigma}_{U}(S_{1})<T+\alpha T\)do
4\(u\leftarrow\arg\max_{v\in V\setminus S_{1}}\left(\hat{\sigma}_{U}(S_{1}\cup\{ v\})-\hat{\sigma}_{U}(S_{1})\right)\)
5\(S_{1}\gets S_{1}\cup\{u\}\)
6 end if /* Phase 2 */
7.\(\epsilon_{1}\leftarrow\frac{\epsilon}{2(1-1/\epsilon)-\epsilon}\) */
8.\(t_{0}\gets k-|S_{1}|\), \(\delta_{1}\leftarrow\frac{\delta}{6}\), \(t_{max}\leftarrow\arg\max_{j\in\{t,t+1,t+2,\ldots,k\}}\ln((\binom{n}{j}/\delta _{1})/j\)
9.\(N_{1}\leftarrow\frac{\ln(1/\delta_{1})}{\epsilon_{1}^{2}}\), \(N_{max}\leftarrow\frac{(2+\frac{2}{3}\epsilon_{1})n\ln((\binom{n}{j_{max}}/ \delta_{1})}{t_{0}\epsilon_{1}^{2}}\)
10.\(i_{max}=\lceil\frac{N_{max}}{N_{1}}\rceil\), \(\delta_{2}\leftarrow\frac{\delta}{3t_{max}}\)
11.