An Effective Algorithm For Influence Maximization Problem In Social Network

The influence maximization in social network is important for marketing,ad-vertising.Given a graph which represents a social network and a specific informa-tion diffusion model,influence maximization problem is the problem how to select seed nodes to influence as more nodes as possible.There are two frequently-used model of information diffusion,independent cascade model and linear threshold model.It' s too difficult to calculate the influence directly.It ' s an efficient method to approximate the influence spread by the Monte Carlo simulations.It' s very time-consuming and too expensive to be applied in a large scale social network.Greedy algorithm is a classical algorithms for influence maximization problem,but it' s very expensive.There are many researches about,designing meta-heuristic agorithms for influence maximization problem recently.They perform well in experimental researches.Pareto optimization for subset selection,which is called POSS,is one of the meta-heuristic algorithms.In this thesis we use POSS to solve influence maximization problem and proposed two new versions.The dynamic mutation an help to jump out local optima with a dynamic mutation rate.We propose the dynamic mutation based Pareto optimization for subset selection which is called DM-POSS.We prove it can achieve the best known approximation guarantee on influence maximization.The experimental results show that DM-POSS finds better solutions than POSS.The crossover mutation is very important in genetic algorithm.We propos an-other algorithm,Pareto optimization for influence maximization(POIM),by us-ing crossover operator.POIM runs faster than POSS and find better solutions on experiments.