# Influence Maximization in Social Network Considering Memory Effect and Social Reinforcement Effect
## 2 Related Work  
Research in the area of viral marketing [12; 13; 14; 15] takes advantage of social network, wherein friends recommend a product to their friends, who in turn recommend it to others, and so forth, creating a cascade of recommendations. In this way, the ad of the product can spread through the network from a small set of initial nodes to a potentially much larger group. [PERSON] and [PERSON] [3] first formulated viral marketing on social network as an influence maximization problem. They modelled the problem using Markov random fields and proposed heuristic solutions. [PERSON] et al. [4] studies influence maximization as an optimization problem. They showed that the problem is NP-hard under both Independent Cascade (IC) and Linear Threshold (LT) Models, and proposed a greedy algorithm to solve the problem. In an effort to improve the efficiency of greedy algorithms, [PERSON] et al. [16] recognized that not all remaining nodes need to be evaluated in each round and propose CELF. [PERSON] et al. further proposed CELF++ [17], that has been shown to run from 35% to 55% faster than CELF. Both CELF and CELF++ are based on sub modularity. In [18], [PERSON] et al. studied the efficient influence maximization from two complementary directions. One is to propose New Greedy to improve the original greedy algorithm, and the second is to propose Degree Discount heuristics that improves influence spread. [PERSON] et al. devised several heuristic algorithms for influence spread computation [18; 19; 20]. In Degree Discount [18], the expected number of additional nodes influenced by adding a node v in the seed set is estimated based on v's one hop neighborhoods. [PERSON] et al. [21] proposed a new framework, called community-based influence maximization (CIM), to tackle the influence maximization problem with an emphasis on the time efficiency issue. In [19; 20], two approximation algorithms, PMIA and LDAG are proposed to compute the maximum influence set under IC and LT models, respectively. In LDAG, it has been proven that under the LT model, computing influence spread in a DAG has linear time complexity, and a heuristic on local DAG construction is provided to further reduce the computation time. [PERSON] et al. [5] and [PERSON] et al. [6] independently proposed the time-critical influence maximization problem, in which the propagation model considers time constrain. They proved the monotonicity and sub modularity of the time constrained influence spread function and propose algorithms to solve the problem. [PERSON] et al. [22] argued that, in more real-world cases, marketers usually target certain products at particular groups of customers. So, they proposed the labeled influence maximization problem, which aims to find a set of seed nodes which can trigger the maximum spread of influence on the target customers in a labeled social network. In order to build a more realistic problem of viral marketing, [PERSON] and [PERSON] further proposed the budgeted influence maximization problem (BIM),which involves selecting a set of seed nodes to maximize the total number of nodes influenced in social networks at a total cost no more than the budget [7]. [PERSON] et al. studied influence maximization from a novel data-based perspective. They introduced a new model, which is called credit distribution, that directly leverages available propagation traces to learn how influence flows in the network and uses this to estimate expected influence spread [23]. [PERSON] et al. [24] proposed a novel network model and an influence propagation model taking influence propagation in both online social networks and the physical world into consideration by using mobile crowd sourced data. [PERSON] et al. [25] proposed an extension to the Independent Cascade Model (ICM) that incorporates the emergence and propagation of negative opinions which is commonly acknowledged in the social psychology literature. [PERSON] et al. [26] studied a new interesting problem on social network influence maximization recently.