Research On Influence Maximization Problem In Social Networks Based On Memetic Computing

Social influence analysis is an important aspect in social network analysis. And one of the social influence analysis fields, influence maximization in social networks, has received more and more attentions. More and more social network cites emerge and provide rich research data and research platforms for the problem. The influence maximization in social networks mainly focuses on how to select limited influential customers who can influence the most other customers in social networks. This problem is meaningful for the viral marketing, recommendation system, incident outbreak and so on. Recently, more and more algorithms for the problem have been proposed. There are mainly three kinds: the improvements on the greedy algorithm, the community-based influence maximization algorithms and the heuristic methods based on the property of nodes in social networks. The improvements can obtain the same results as that of the greedy algorithm, however they need long running time. Therefore, they can't apply to the large-scale networks. The community-based algorithms need less time than the improvements. The efficiency of the heuristics is highest, but they produce poor influence spread.Memetic algorithm is combination of a population-based procedure and an individual-based procedure. It can overcome their shortage and produces a high efficiency and effectiveness.In this thesis, we make use of the advantages of the community property of social networks and memetic algorithm to solve the influence maximization problem in social networks. The main works are as follows:(1)We study the influence of the similarity between nodes in the social networks on the influence maximization problem. And we propose a similarity-based degree centrality method. In this method, we try to exclude the similar nodes of the high degree nodes to avoid the influence overlapping between similar nodes.(2) We apply the memetic algorithm to the influence maximization problem and proposed a problem-specific memtic algorithm. The proposed algorithm combines the genetic algorithm and a similarity-based local search strategy so that it is more efficient than thetraditional genetic algorithms. Meanwhile, we use the community of the networks to narrow down the search space of influential nodes so that we can improve the efficiency of the algorithm.(3) We make different experiments on three-scale real-world networks. For(1), we test the influence of similarity between nodes on different networks and the effectiveness of our proposed algorithm. And for(2), we first test the effectiveness of the network clustering and the local search strategy. And then we test the effectiveness and the efficiency of our proposed memtic algorithm.