Research On Incremental Algorithm For Influence Maximization In Social Networks

In recent years,many rapidly emerging online social networking platforms have become important ways for people to spread information and influence others;Influence Maximization(IM)is an important issue in the analysis of social network information dissemination,and it is a key role in many applications such as word-of-mouth marketing,public opinion control,and network monitoring;this problem and its derivative problems include the topic maximization influence and the Correlated Influence Maximization(CIM)problem,etc.,which have been extensively studied.The IM problem aims to find out the most influential k users in the network,and sends out the information from the selected users with a certain propagation model,so that the total number of affected users is the largest.Most traditional influence maximization algorithms only focus on static social networks.However,the social network topology naturally has dynamic characteristics,and traditional algorithms are not applicable.This paper studies the problem of influence maximization in dynamic networks,and proposes an incremental algorithm for influence maximization based on hop.The main research contents of the paper are as follows:(1)Research on the Incremental Algorithm of the IM Problem under the Hop Independent Cascade ModelIn order to solve the problem of updating the most influential seed set in a dynamic network,based on the hopping strategy,an incremental influence maximization algorithm for an independent cascading propagation model is proposed.The algorithm uses the characteristics of localized propagation to quickly evaluate the upper limit of influence gain of nodes involved in network changes,and compares the previous output results to identify results that do not need to be changed;at the same time,it quickly updates the influence nodes that may require changes.Experimental results on large-scale real data sets verify the efficiency of the proposed algorithm;in the best case,the proposed algorithm runs several orders of magnitude faster than other existing algorithms.(2)Research on the Incremental Algorithm of the IM Problem under the Hop Linear Threshold ModelIn order to study the application of the herd mentality of the user in the influence maximization,based on the hopping strategy,an incremental influence maximization algorithm for an linear threshold propagation model is proposed.The algorithm dynamically maintains the known influence value of users,constructs candidate sets to provide users who are most likely to replace seed users after dynamic changes,and thus incrementally updates the seed set to obtain the latest influence diffusion range.After the experiment of multiple data sets,under the optimal situation that the difference between the influence diffusion range and the influence diffusion range does not exceed 10%,the running time of the proposed algorithm is several to tens of times faster than the comparison algorithm.(3)Research on Incremental Algorithm of CIM Problem under the Hop Linear Threshold Model of CorrelationIn order to explore the problem of maximizing the influence of positive correlative,on the basis of the correlated linear threshold model,a correlated linear threshold propagation model based on hop is proposed,and then an incremental algorithm is proposed.The algorithm analyzes the changes in the network structure and maintains the effective node set in real time,so that the seed set is incrementally updated.The verification of the real network data shows that the proposed algorithm can complete the update of the new seed set more quickly,and the influence of the diffusion range does not lose similar algorithms.In the best case,it runs about tens of times faster than other comparison algorithms.