Research On The Method Of Influence Maximization About Associative Information Propagation

With the rapid development of the mass media,such as Weibo and Wechat,it becomes more efficacy and more useful to exchange the information through the social network.Through the analyze of the information propagating mechanism,we can make better use of social network resources to propagate information and monitor trendy topic.For example,The influence maximization problem is to identify a set of nodes with largest influence under a certain information propagation model.This is a vital application in this area.For the different actual situations,the experts and scholars have proposed many models,some of them reflect the decay of information propagation in the process of transmission,some of them reflect multiple information competition within a social network.However,there are less propagation model about associative information that one's propagate will boost another.But in our daily life,it is not rare to see this.This text is under the background of the information propagation in the social internet,focusing on the propagation model which reflect one kind of information's propagation will boost another and on the seeds selection method based on the model.We can conclude this text in these four points:(1)We further our research based on the LT model and then propose an AILT model where one kind of information accelerates another by showing the range of the edge weight.Also,we suggest a new approach of getting edge weight via the structure of network and historical data.It is then proved that the expectation of information's propagation under AILT model will increase through comparison.(2)We certify that the influence maximization problem of the seed set selection under AILT model is a NP-hard problem.Greedy algorithm can be used to reduce the time complexity of influence maximization problem under AILT model to polynomial time.It is also proved that the propagation income function under AILT model is submodular,monotone,and non-negative.Thus,it is guaranteed that the worst result which is worked out via greedy algorithm is no less than 1-1/e ratio of the optimal result.(3)When the scale of network is relatively large,the time cost,using greedy algorithm,is unacceptable.Inspired by Chen Hao,we propose CIR seeds selection algorithm.The key of the algorithm is to estimate the potential contribution value of the edge and candidate nodes for the information propagation.We exploit the potential contribution value as guidance information to select seeds.Because the estimation of the potential contribution value is limited to a small area network centered on the node,the efficiency is much more increased compared to the greedy algorithm.And due to the relative independence of the potential contribution estimation,we extend the CIR seeds selection algorithm to PCIR algorithm,and realize it via Spark framework.(4)We exploit,HepTh,Web-Stan,and Pokec,three real datasets with different scales and type to test the model and algorithm proposed by this essay.The results prove that the AILT model plays a better role in spreading information,and that the PCIR algorithm is efficiency and effective.