Multiple Influence Maximization Research In Social Networks

Influence Maximization(IM)problem is to select k seed users to maximize the influence spread from social networks.As a kind of social analytical technique and a research hotspot,it has broad application such as information popularization and product recommendation.However,previous researchers did not consider the following scene that,taking product recommeadation as an example,a company may plant to promote several kinds of products and these categories do not compete with each other.Besides,as the limit budget constraint k,each user has different preferences for different categories,which matches that a variety of information propagate simultaneously in the same social netowrk and each user's acceptance of information is dominated by their own subjective intention.Therefore considering this scenario,we propose the Multiple Influence Maximization(MIM)problem based on the following properties:(1)one seed user can accept one or several kinds of products recommendation;(2)non-seed user can freely accept recommendation from its social friends.For Property(1),if a seed user can freely accept several categories recommendation,we propose the Repetitive Multiple Influence Maximization(RMIM)problem and when a seed user can only accept one category recommendation,we propose the Non-Repetitive Multiple Influence Maximization(NRMIM)problem.Traditional greedy algorithm is an effective solution for IM problem,but it cannot be applied into MIM problem directly.Therefore,in this paper we propose the RMIM-Greedy and NRMIM-Greedy framework for RMIM and NRMIM problem respectively.Simultaneously,to simplify the influence computation and consider that influence can propagate alone multiple social paths,we also propose a new-style influence computation model and apply this model into MIM.Simultaneously,considering large scale social network,we propose independentpartition-based algorithms,namely Parallel RMIM-Greedy and Parallel NRMIM-Greedy.Applying our influence computation model,for RMIM problem,Parallel RMIM-Greedy guarantees the approximation radio of 1-1/e,where e presents the natural logarithm base.And for NRMIM,we find the approximation property with accumulative error bound regardless of influence propagation model.Our extensive experiments show that our proposed parallel algorithms outperform common heuristic algorithms and have faster running time.