Influence Maximization On Social Networks Based On Evolutionary Algorithm

With the tremendous innovation of information technology,especially the Internet,social networking sites such as WeChat and Facebook have been booming in everyone's life.The problem of Influence Maximizing which has been extensively studied in recent years is a key topic in the field of social networking.The purpose of it is to find an individual group(seed node set)that can achieve the greatest influence spread in a social network.Researchers have proposed many effective algorithms to solve this problem.However,most studies only focus on how to efficiently find target nodes in a social network,ignoring the complexity and diversity of real social networks,such as the cost of activating target nodes.In this thesis,evolutionary algorithms are used to study the influence maximization problem in social networks,and we discuss three research work in detail.Firstly,a Multi-agent Genetic Algorithm(MAGA)is proposed to solve the general influence maximization problem.Then,the deficiencies of the previous research are further supplemented.After repeatedly considering the characteristics of the real social network,we proposed an Influence Maximization-Cost Minimization problem model,and a Multiobjective Discrete Particle Swarm Optimization Algorithm(MDPSO)is proposed to solve the problem.Finally,we propose a social network influence maximization enhancement algorithm model,which is used to further enhance the influence of the seed nodes in the network.The specific work is summarized as follows: A Multiagent Genetic Algorithm for Influence Maximization in Social Networks: Multi-Agent Algorithm has excellent performance in large-scale networks.In this thesis,multi-agent evolutionary algorithm is applied to the problem of maximizing the impact of social networks,and we proposed the MAGA-IM.In this thesis,we design the neighborhood competition operator,the enhancement operator,and the self-learning operator to quickly select the most influential propagation in target networks.In addition,in order to accelerate the convergence of MAGA-IM,we also designed the specific population initialization method.We conduct experiments in four real-world social networks with different scales and average degree and compare with different impact assessment methods.The experimental results show that our proposed algorithm can effectively solve the problem of maximizing the impact of various networks.Influence Maximization-Cost Minimization in Social Networks Based on a Multi-objective Discrete Particle Swarm Optimization Algorithm: The traditional impact maximization problem model usually assumes that the activation cost of each individual in the seed set is the same,ignoring the cost difference between them,and this point is often inconsistent with real social network features.In fact,if a company plans to market its products or ideas,it will pay different amounts to each individual in the seed collection based on the individual's level of influence in the network,and all companies want to get the most influence spread at the lowest acceptable cost.Inspired by this,we establish a new problem model called Influence Maximization-Cost Minimization(IM-CM),which accurately captures this feature of real-world networks.In order to solve this problem,we propose a multi-objective discrete particle swarm optimization algorithm that takes into account the total cost and total impact.It aims to find the maximum influence value that can be obtained at each cost.For decision makers,there are a number of options available so they can choose based on their budget.We test our algorithm on three different real-world social networks.The experimental results show that our proposed algorithm can effectively and efficiently solve the problem.Target Rewiring for enhancing the influence spread in social networks: The social network is a network with very high frequency of change.When the network changes,changing the seed node is a high costly choice.How to further improve the overall influence of seed node groups in the network under a limited resource with a small cost is a problem worth studying.In response to this phenomenon,we propose a Target-Rewiring method to further improve the overall influence of the seed node group in the network.We test the performance of our algorithm improving the effect in three real networks.Experimental results show that our proposed strategy can greatly increase the impact of the network at a small cost.When the seed node set is determined,its influence is enhanced.Each node has how the seed nodes can enhance the overall influence of the network through internal cooperation.In the dynamic network,when the seed node is fixed,how it should change to always maximize its impact on the target network.