Research On The Methods Of Influence Maximization In Social Networks

Social network is a relatively stable relationship system formed by the interaction of members of society.The members in social network can influence one another.When someone accepts a new idea or product,he or she may recommend it to his or her friend,and his or her friend,in turn,will probably recommend it to their friends.This is "viral marketing" and it can influence a large population in social network.With the development of Internet technology and Web2.0,online social network has become an important communication platform and has influenced people's offline life.Therefore,influence maximization in social networks has become a hot research concern home and abroad,which focuses on finding a small subset of K nodes in a social network that could maximize the number of nodes influenced.The study of influence maximization has great theoretical and practical significance in such fields as product marketing,policy promotion,infectious disease control,and rumor containment,etc.The research studies the influence maximization in information propagation process in relation to different application scenarios,as in the following.First of all,aiming at the problem in the traditional Greedy algorithm with high time complexity,an IM_GA algorithm is proposed based on the genetic algorithm.In order to avoid precocious phenomena,joining simulated annealing algorithm to genetic algorithm periodically,an IM_GA_SA algorithm is put forward.In order to improve the running speed,expected influence spread is used as the measurement in the computation of seed set's influence range value.The effectiveness of the algorithms is verified by experiments.Secondly,a user influence ranking method named UPR is proposed to overcome the problem of using only user's properties or web page ranking method to measure user's influence in Microblog.Meanwhile,an influence maximization algorithm IM_UPR is proposed as well to maximize user's influence in Microblog.The UPR method is based on the PageRank algorithm and combined with the rule through data analysis.The initial value of user influence ranking is measured through followers' number,recent tweets' quality and user's active degree.The IM_UPR algorithm is put forward based on the UPR method and the forwarding path.The reasonability of UPR and effectiveness of IM_UPR are verified by experiments.Thirdly,a new information dissemination model named MTIC is proposed based on the Independent Cascade Model as the initial user tends to spread many times.The model MTIC is proved to be monotone and submodular.In order to achieve the optimal combination of the budget and influence range,an influence maximization algorithm,named BCIM,is proposed based on the idea of dynamic programming.In BCIM,the candidate seeds are divided into several groups and one seed is selected at most in each group.In order to reduce the computational complexity,the node's influence range is calculated based on the expected influence on the nearby neighbors in the shortest path.The effectiveness of the algorithms is verified by experiments.Finally,an influence maximization algorithm,DIM,is proposed in dynamic network for the real-life network change over time.In this algorithm,the dynamic network is expressed in the form of snapshots,the maximum influence range of node is generated based on the information dissemination model in dynamic network,and then the greedy idea is used to find the seed with the largest increment.In order to reduce the computational complexity,the activation probability of a node influenced by all seeds is approximated to the sum of the activation probability influenced by each seed in the computation of incremental influence of node.The effectiveness of the algorithms is verified by experiments.