Study Of Influence Maximization In Social Networks Based On Memetic Algorithm And Distributed Parallel Computing Of Spark

With the development of Internet technology and the arrival of big data era,social networks have gradually become the main medium for people to interact and share information.In recent years,more and more businesses and enterprises have started to use social networks to promote their products.This new marketing model can often bring more marketing effectiveness at a lower cost.The problem of influence maximization aims to select a certain number of influential individuals from the social network,which are used as the source of information to maximize the influence spread in the whole network.In addition to the research field of information spread in social networks,the problem of influence maximization has also been applied to the public opinion monitoring and epidemic prevention and other fields.In recent years,more and more scholars have devoted themselves to the study of the problem of influence maximization and proposed many solutions.These algorithms can be roughly divided into the following three categories: the greedy algorithm based on hill-climbing mechanism and its improved algorithms;heuristic algorithms based on the characteristics of social networks;optimization algorithms based on objective functions.Among them,the greedy algorithm and its improved algorithms have high accuracy but their efficiency is low.So,they are not suitable to solve the problem of influence maximizing in largescale social networks.On the contrary,heuristic algorithms have high efficiency but they are poor in accuracy and stability.In order to solve the problem of influence maximization and the shortcomings of existing algorithms,this thesis studies the problem of influence maximization in social networks from the following aspects:In this thesis,we innovatively propose an algorithm for the influence maximization in social networks based on community division and Memetic algorithm.Using the community structure of social networks,this algorithm effectively reduces the selection space of the initial active nodes and improves the efficiency of the algorithm by filtering important communities and candidate nodes.At the same time,this algorithm uses Memetic algorithm to optimize the function of 2-hop influence spread.In order to solve the problem of influence overlapping between the initial active nodes,this algorithm proposes the concept of similarity of node degree and applies this strategy to the operations of initialization,crossover,mutation and local search of Memetic algorithm.Through comparative experiments in real networks,it can be proved that this algorithm can not only effectively solve the problem of influence maximization in social networks but also have good efficiency.In order to deal with the challenges brought by super large scale social networks,this thesis proposes a distributed parallel algorithm framework to solve the problem of influence maximization in social networks based on the computing platform of Spark.Making use of the distributed parallel graph calculation framework of Spark Graph X,this algorithm realizes and improves the algorithm proposed above.Learning from parallel genetic algorithm,this distributed parallel algorithm designs the migration operator,which can not only effectively avoid the immature convergence of the subpopulation but also improve the accuracy and efficiency of the algorithm.Through experiments on a super large scale social network,it is proved that the distributed parallel algorithm can effectively solve the problem of influence maximizing in an acceptable time,which also provides a reference for the study of large-scale social networks in the era of big data.