Article Preview
Top1. Introduction
With the continuous development of social networks, the influence of social networks has attracted more and more attention. In the field of social network influence research, influence maximization is its research hotspot. The problem is actually an optimization problem based on a specific propagation model to find a set of initial propagation nodes in social network, through which the final propagation influence scope is the largest. Richardson et al. first proposed the influence maximization problem, and then many researchers conducted in-depth research on the problem from the aspects of influence propagation model and optimization algorithm (Nekovee et al., 2008; Wang et al., 2012; Yang et al., 2020; Yuan et al., 2022).
Influence propagation model can be used to describe the dynamic propagation process of influence in social networks. It is the premise and basis of studying the influence maximization in social networks. At present, the popular information propagation models include: infectious diseases model (Hethcote, 2000) independent cascade (IC) model (Goldenberg et al., 2001) and linear threshold (LT) model (Zhou et al., 2015). Although these common models describe the process of information propagation and diffusion in social networks to a certain extent, due to some limited conditions, these models are not very consistent with the influence propagation in real social networks. Therefore, many researchers proposed a large number of improved influence propagation models based on these models and combined with the real influence propagation in real social networks. Bazgan et al. extended the IC model and LT model (Bazgan et al., 2014), and made the two extended propagation models convert to each other. Wan et al. defined a dynamic function to represent the influence relationship between users, and proposed a fully cascaded information propagation model based on the influence relationship between users (Wan et al., 2019). Tian et al. started with the content of information propagation, introduced the topic of information propagation into the information propagation model, and pointed out that the influence among users is obviously different for different topics (Tian et al., 2020). Li et al. proposed the influence maximization model based on competition and promotion (Li et al., 2020). Chen et al. Proposed M-TLT propagation model based on topic perception (Chen et al., 2020).
Cristina et al. studied the influence maximization problem in social networks based on IC model and LT model, and proved that the problem is an NP-hard problem (Cristina et al., 2013), and a greedy algorithm with approximate solution of 
is designed to approximately solve the problem by selecting the nodes with the greatest marginal influence in the network. However, due to the low efficiency of greedy algorithm, it is not suitable for large-scale social networks. So researchers proposed many optimization algorithms for the computational performance of the algorithm. Leskovec et al. proposed Cost-Effective Lazy Forward (CELF) algorithm by using the submodular characteristics of the influence function between nodes. The algorithm reduces a lot of unnecessary calculations and greatly reduces the time complexity of greedy algorithm (Li et al., 2020). Goyal et al. improved the efficiency of CELF algorithm by using the submodularity and special data storage structure. Experiments show that the optimized CELF algorithm has a performance improvement of more than 17% (Goyal et al., 2011).