# Influence Maximization with Priority in Online Social Networks
## 1 Introduction  
Presently, Online Social Networks (OSNs) have become an important platform in communication as well as e-commerce. Companies and businesses have leveraged a rapid spread of information thanks to the \"word of mouth\" effect among friends in social networks as a powerful tool for viral marketing. For instance, companies can provide some ones with free samples over an OSN so that much more people may know about their products and they have more chances to sell them. Influence Maximization (IM) problem [1], a key problem in viral marketing, has been extensively studied for this decade due to its tremendous value in business, viral marketing and influence propagation. Basically, IM aims to find some nodes (called _seedset_) in a social network to inject opinion, innovation or influence that can effect the largest the number of nodes. [PERSON] et al. [1] first studiedIM as an optimization problem combined with two well-known models, Independent Cascade (IC) and Linear Threshold (LT). Since IM is NP-hard, they designed a native greedy algorithm that returned an \((1-1/e)\)-approximation solution. The research shows that IM is not only a potential commercial role in viral marketing [2, 3] but also a foundation of various applications in many fields such as epidemics control in social network [4, 5, 6, 7, 8], social network monitoring [9, 10], recommendation system [11], etc. Hence, IM has been extensively studied recently [2, 4, 12, 13, 14, 15, 16, 17, 18, 19]. Although IM has a lot of great applications in viral marketing, previous studies ignored considering the impact on priority users who could play an important role for effectiveness of viral marketing campaigns. In fact, companies often prioritize specific potential customers, who are financially competent or suitable for their products. For examples, if a company produces baby diapers, they tend to introduce the product to married women aged 20 to 45. Supposing that they have some data about user accounts on a social network, hence they launch a promotion with suitable amount of gifts to married female users via this social network. If we only care about the number of influenced individuals, as in the case of IM, we will not evaluate the impact to the potential users and lead to wrong selection of a seed set. Figure 1 shows an example. This network contains 8 nodes and 9 edges, the priority set is \(\{b,d\}\) and the weight of each edge (or influence probability) is assigned to 1. Considering the case when the budget \(k=1\) (number of seed nodes), the optimal solution of IM is \(\{f\}\) influences to 6 nodes including \(\{f,d,g,c,e,h\}\) except \(b\). Hence, IM cannot take effect to all priority nodes.The solution must be \(\{a\}\) that has the total influence is only 5. Motivated by such interesting scenarios, in this paper we investigate the _Influence Maximization with Priority_ (IMP) problem, which takes into account the priority constraint for influence process. Given a social network \(G=(V,E)\), a _priority set_\(U\subset V\), a budget \(k\) and a _priority threshold_\(T\), \((T\leq k)\), the goal is to find the seed set \(S\) sized at \(k\) so that it influences to \(U\) at least \(T\) and the influence of the cascade is maximized. In fact, IMP is more suitable than IM. Besides, it generalizes IM problem. Nevertheless this problem faces with complicated challenges caused by the constraint of priority. To address this problem, we propose two approximation algorithms, _Integrated Greedy_ (IG) and _Integrated Greedy-based Sampling_ (IGS), with provable theoretical guarantees. IG meets the theoretical guarantee based on a modification of the natural greedy algorithm while IGS is an efficient randomized approximation algorithm based on sampling method [13, 14, 15, 20]. This algorithm combines two novel techniques. Firstly, we propose Targeted Reverse Reachable (TRR) concept by modifying the Reverse Reachable Sampling (RR) technique [13, 14, 15, 20] to estimate influence from a seed set to a given priority set.