| Research on the problem of influence maximization has a wide range of applications in the field of social networks.In recent years,research on the problem was mainly based on the common static graph,but in real-life social networks nodes tend to have connections only at some specific time,and have a certain order of interaction,networks with such characteristics were usually represented as temporal graph.The temporal graph contains the time attribute information of the connections between nodes,which is a more realistic depiction of the real social situation.It is of more practical significance to study the maximization of influence with it as the object.therefore,the maximization of influence on temporal graph was studied in this article.Firstly,To solve the problem that information propagation in temporal graph has time series characteristics,existing information diffusion models cannot accurately simulate the process of information diffusion in temporal graph,an information diffusion model IDMT based on temporal graph was proposed.The concept of node initiation active time was introduced in the model,and a method of calculating the propagation probability between temporal graph nodes was defined according to the frequency of interaction between nodes.Three different node states were defined according to the individual’s different responses to information,and the process of information transmission in the temporal graph was described.which makes it more suitable for real social situations.Secondly,most of the existing maximizing influence algorithms based on temporal graph were not applicable for large-scale networks due to the low time efficiency or narrow influence range.Therefore,the seed node mining algorithm named CHG combining heuristic algorithm and greedy strategy was proposed.The algorithm combined the social breadth of nodes with the depth of information diffusion to heuristically evaluated the impact of temporal graph nodes,filtered and constructed a set of candidate seed nodes based on the impact evaluation results,and then solved the overlap of influence ranges between nodes by calculating the marginal effects of candidate nodes,ensuring the optimal combination of seed nodes.Thirdly,to solve the problem of seed node failure,a two-stage substitution seed node mining algorithm named TSSM based on temporal graph was proposed.The algorithm was divided into two stages: pre-selection and final selection.The pre-selection stage started from the local invalid seed nodes,defined the concept of node replaceability,and builded a substitution list for the invalid seed nodes according to their size.In the final stage,the marginal effects of the candidate nodes in the substitution list was calculated to further select the substitution seed nodes that made the network influence reach the global optimum.Finally,the information diffusion model named IDMT,algorithm named CHG and algorithm named TSSM were experimentally analyzed on three real temporal network datasets,and compared with the existing methods to verify the effectiveness of the algorithm proposed in this paper. |
