# Influence Maximization with Priority in Online Social Networks
## 1 Introduction
[13] first presented an \((1-1/e-\epsilon)\)-approximation algorithm with probability at least \(1-\delta\) in \(O(kl^{2}(m+n)\log^{2}n/\epsilon^{3})\) time complexity by introducing Reverse Influence Sampling (RIS) model. This model has formed the foundation for further algorithm development. [14; 15; 20; 23]. From then on, many works expanded IM in contexts of viral marketing. [PERSON] et al. [24] investigated the Budget Influence Maximization (BIM) problem which considered the cost of selecting a node and proposed a \((1-1/\sqrt{e}-\epsilon)\) approximation algorithm. The authors in [2] studied the a generalization of IM and BIM problems, called Cost-aware Targeted Viral Marketing (CTVM). In this work, each node \(u\) had an arbitrary cost \(c(u)\) and a benefit \(b(u)\) and the goal of CTVM was to select a seed set within a given budget so that the total benefit was maximized. We believe that this is the closest problem to our work. In CTVM problem, we can set parameters that maximize the influence on a given target set of users but cannot simultaneously maximize the influence of the others as in our problem. Later, several works improve the approximation as well as the scalability of CTVM algorithms [25; 26]. Moreover, there are also many variants of IM problem that were studied. Some works studied the constraints of IM such as [17; 18; 27], in which edges were associated with a topic influence weight. These problems aimed to find a set of \(k\) users that maximized influenced users according to a topic query. However, the proposed algorithms did not provide any theoretical guarantee. [PERSON] et al. [PERSON] et al. (2018) proposed the Location-aware Influence Maximization (LIM) problem with the goal was to select the \(k\)-seed set so that the number of influenced nodes in the given query region was maximized. [PERSON] et al. (2018) investigated the Distance-aware Influence Maximization (DAIM) problem which considered the role of distance between users and the promoted location in seed selection. They extended a RIS process model and provided an unbiased estimator for the DAIM problem. Besides, some works investigated the problem of Competitive Influence Maximization (CIM), which considered the context of IM under the competition of many rivals. [PERSON] et al. [PERSON] et al. (2018) first formulated the CIM problem under a new competitive propagation model which was an extension of IC model. [PERSON] et al. [PERSON] et al. (2018) investigated CIM under the combating with negative opinions based on an assumption that negative information was often more attractive than official information. Some authors considered the problem under many different cases in viral marketing, such as proposing a distance-aware problem [PERSON] et al. (2018), expanding the LT model to reflect competition [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018), proposing a heuristic algorithm [PERSON] et al. (2018), etc. Recently, some authors studied the selection of seed nodes in a social network to influence groups of users or communities instead of individuals [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018). They argue that in real-world scenarios, creating impact on groups is more beneficial than the individuals in a network. [PERSON] et al. [PERSON] et al. (2019) investigated the Fairness Group Maximization problem with two fairness criteria including maximin fairness and diversity. While the maximin fairness aimed to maximize the minimum influence nodes of any per their population, the criterion of diversity was an alternate fairness concept by extending the notion of individual rationality to group rationality. They proposed an approximation algorithm based on multi-submodular objective function processing techniques. More recent, the authors in [PERSON] et al. (2018) proposed exact algorithms for fairness group influence with multiple criteria based on mix integer linear programming formulation on a specific set of sample graphs under IC model.