Research On Influence Maximization Algorithm In Social Networks

With the rapid development of graph theory and network science,complex networks as a powerful tool can be easily used to model and analyze networked systems,and further disclose the mechanisms.With the large scale popularization and rapid development of the Internet in recent years,more and more people are transferring their offline life and production activities to online,and their various social interactions have formed various social networks,It is of great practical significance to analyze these network data.For example,“viral marketing”uses a small number of influential groups in the network to promote Wide range of products,through word of mouth to reach the maximum scope of influence.How to find the most influential k nodes from the network,called seed nodes,so that it can reach the maximum influence spread,that is,the problem of influence maximization.Finding the most influential node set is a challenging problem.A simple method is to use some traditional key node identification algorithms,such as median centrality,feature centrality,KShell,and Page Rank sort nodes,and then select the largest k nodes as seed nodes.However,the influence of the seed set is not equal to the simple superposition of the influence of each seed node,so the seed nodes selected using this simple method will have a serious problem of overlapping influence.In order to solve the overlapping problem,this thesis proposes a new influence maximization algorithm called GDIM.The main idea of the algorithm is to use each node in the network as a single origin to trigger influence propagation,From this,a new network containing the influence relationships of each node is called“INFNET”,and then by finding the minimum dominant set of INFNET,we can get a most influential candidate seed set that can activate the entire network,Finally,the greedy algorithm is used to select the most influential seed set.In order to verify the effectiveness of the GDIM algorithm,it is compared with the degree centrality,feature centrality,K-Shell,Page Rank,Spring Rank,and the LDAG algorithm on the linear threshold model on synthetic networks and real networks.Experimental results show that the GDIM algorithm is superior to other algorithms on both types of networks.at the same time,the experiment also find that influential nodes identified by our algorithm tend to be located more widely over the networks to avoid more centralized high-degree nodes or core nodes so that the overlap problem can be alleviated effectively.