# Influence Maximization with Priority in Online Social Networks
## 6 Conclusions  
In this paper, we investigate the IMP problem, which is a variant of the IM problem with priority constraint that arises in a realistic scenario in which companies or organizations often prioritize influencing potential users during their viral marketing campaigns. The goal of the IMP problem is to select a seed set with \(k\) nodes can influence of a given priority set \(U\) greater than a threshold \(T\) which adjusts the influence of the seed set to the priority set. Although the objective function (influence spread function) is still a monotone and sub-modular function, but when considering the priority constraint the state-of-the-art IM algorithms cannot be applied. To address this challenge, we propose two algorithms with provable theoretical guarantees, called IG and IGS. We show that IG provides a \(\left(1-(1-\frac{1}{k})^{t}\right)\)-approximation solution; IGS is an efficient randomized approximation algorithm based on sampling method that returns a \(\left(1-(1-\frac{1}{k})^{t}-\epsilon\right)\)-approximation solution with probability at least \(1-\delta\) with \(\epsilon>0,\delta\in(0,1)\) as input parameters of the problem. Experiments on real world social networks show our algorithm outperforms state-of-the-art IM algorithms including DSSA [15], BCT [2] and OPIM [23] in terms of influences, running time, and memory used. \begin{table}
\begin{tabular}{l l c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{6}{c}{**Budget k**} \\ \cline{3-8}  & & **150** & **160** & **170** & **180** & **190** & **200** \\ \hline \multirow{4}{*}{**Dataset**} & IGS & **9.90** & **9.90** & **9.90** & **9.89** & **9.89** & **9.95** \\ \cline{2-8}  & DSA & 22.84 & 22.84 & 22.84 & 22.84 & 22.84 & 22.84 \\ \cline{2-8}  & BCT & 1023.79 & 1017.52 & 1021.60 & 1012.21 & 1020.18 & 1020.74 \\ \cline{2-8}  & OPIM-C & 47.76 & 47.91 & 48.03 & 48.11 & 48.30 & 48.46 \\ \cline{2-8}  & Degree & 49.14 & 49.18 & 49.48 & 49.68 & 49.86 & 50.13 \\ \hline \multirow{4}{*}{**Dataset**} & IGS & **16.82** & **16.79** & **16.81** & **16.81** & **16.82** & **16.82** \\ \cline{2-8}  & DSSA & 30.48 & 28.07 & 28.07 & 28.07 & 28.07 & 30.48 \\ \cline{2-8}  & BCT & 30.35 & 30.35 & 30.39 & 30.39 & 30.39 & 30.39 \\ \cline{2-8}  & OPIM-C & 27.16 & 27.20 & 42.00 & 27.22 & 27.25 & 27.30 \\ \cline{2-8}  & Degree & 27.98 & 28.08 & 43.77 & 28.19 & 28.27 & 28.41 \\ \hline \multirow{4}{*}{**Dataset**} & IGS & **15.18** & **15.18** & **15.18** & **15.18** & **15.18** & **15.04** \\ \cline{2-8}  & DSSA & 52.12 & 52.12 & 52.12 & 52.12 & 38.50 & 52.14 \\ \cline{2-8}  & BCT & 34.82 & 34.82 & 34.82 & 34.82 & 34.82 & 34.80 \\ \cline{2-8}  & OPIM-C & 87.88 & 88.39 & 88.92 & 89.31 & 90.26 & 90.51 \\ \cline{2-8}  & Degree & 92.26 & 92.71 & 93.33 & 93.88 & 94.68 & 94.98 \\ \hline \multirow{4}{*}{**Dataset**} & IGS & **138.66** & **138.66** & **138.66** & **138.66** & **138.66** & **138.66** \\ \cline{2-8}  & DSSA & 152.90 & 152.87 & 152.87 & 152.91 & 152.91 & 152.83 \\ \cline{2-8}  & BCT & 162.88 & 162.87 & 162.87 & 162.88 & 162.88 & 162.89 \\ \cline{2-8}  & OPIM-C & 475.05 & 373.72 & 373.78 & 373.95 & 477.18 & 477.51 \\ \cline{2-8}  & Degree & 500.87 & 395.00 & 394.26 & 395.35 & 504.52 & 505.26 \\ \hline \multirow{4}{*}{**Dataset**} & IGS & **214.67** & **214.67** & **214.67** & **214.67** & **214.67** & **214.67** \\ \cline{2-8}  & DSSA & 253.14 & 253.14 & 253.14 & 253.14 & 253.14 & 253.14 \\ \cline{2-8}  & BCT & 282.50 & 282.50 & 282.50 & 282.47 & 282.50 & 282.48 \\ \cline{2-8}  & OPIM-C & 877.31 & 874.20 & 722.91 & 876.99 & 886.78 & 877.80 \\ \cline{2-8}  & Degree & 918.53 & 916.23 & 756.93 & 920.00 & 930.33 & 921.95 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: _Memory usage (MB)_ comparisons between IGS and the othersIn the future, we are going to improve our algorithm to expand it with large networks to billions scale with acceptable time. In addition, the problem with multiple priority user sets and thresholds is going to be considered.