Research Of Influence Maximization Algorithms Based On Similarity And Reverse Random Walk

With the rapid development of information technology,various social platforms are constantly emerging,and the interactions between people form the large-scale complex networks.Analysis of network structure and research of information dissemination mechanism in the network have important theoretical significance and practical value for public opinions control,viral marketing,and infection disease control.Influence maximization is one of the important research directions.The problem of influence maximization is to find a part of nodes as the source of information propagation in a network so that the influence scope of these seed nodes is the largest,that is,the spread of information in the network is the widest.In the past decade or so,although many study works have been published on this issue,the current algorithms are still difficult to meet the requirements of high accuracy,low time and low memory when applying to large-scale networks.This paper researches the efficient and effective influence maximization algorithms from the following aspects:Firstly,based on the one-hop neighbors,a similarity framework is proposed to solve the influence overlap problem among seed nodes.By applying the proposed similarity framework to two existing algorithms,DegreeDiscount and PMD,it proves that the proposed similarity framework can improve the accuracy of heuristic algorithms.The second is to propose a two-stage framework to improve the time efficiency of existing greedy algorithms.The framework first selects candidate nodes by improved DegreeDiscount,then uses the existing greedy algorithms to find seed nodes from the candidate nodes.The third is to devise a strategy of reverse random walk to evaluate the importance of nodes.At the same time,in order to speed up the convergence of proposed algorithm,an initial node selection strategy based on degree centrality is proposed.For improving the accuracy of algorithm,the proposed similar framework is used to select seed nodes.Finally,the efficiency and effectiveness of the proposed algorithms are verified by a large number of real-world datasets with various sizes.And the experiments show that the proposed algorithms can achieve the balance of accuracy,time consumption and memory usage.