Research Of Influence Maximization Algorithm Based On Discrete WOA

The influence maximization problem is finding the k nodes with the greatest influence in the network as seed nodes.The information in the network flows from the seed node according to a certain propagation model in the network.The state of other nodes is permanently changed in the propagation process.The final goal is to maximize the total number of nodes in the network that are changed by the seed nodes.The influence maximization problem is NP-hard.Therefore,how to obtain the set of nodes closest to the most influential node set in the network is the core issue in the field of influence maximization.The algorithm research on this issue mainly focuses on two aspects,which one is the algorithm based on greedy strategy and another is the heuristic algorithm based on network topology.But the greedy strategy-based algorithm is inefficient and can not be applied in large-scale networks.And however,the heuristic algorithm based on network topology structure has low accuracy because of the disadvantages such as poor integration of the propagation model.These two types of existing algorithms can not get satisfactory results.In order to overcome the deficiencies of the existing algorithms for influence maximization problem,we optimize from these aspects.Firstly,we propose a new group intelligence heuristic algorithm DiWOA based on discrete whale optimization.We have redefined the particle and evolution strategy of the Whale Optimization Algorithm to apply it to the influence maximization problem.In the initialization stage,we choose the nodes with have the largest degree as the original activation node,and add mutation operations during the evolution of the algorithm,so that the search process has more possibilities.We also use the independent cascade model as the fitness function of the heuristic algorithm and combine the heuristic algorithm with the influence propagation model to ensure the accuracy of the search results to the maximum.Secondly,based on the proposed algorithm,we use the up bound of the influence function to optimize the fitness function of the algorithm.This strategy is applied to our proposed algorithm UB-DiWOA.The algorithm omits many unnecessary calculation processes by calculating the maximum influence of partial node sets,reducing the calculation scale,and improving the algorithm efficiency under the premise of ensuring accuracy.Finally,we also use the matrix analysis theory to further simplify the form of the expected up bound of influence function,so that our UB-DiWOA algorithm can use a more simple form of fitness function to maximize the impact when satisfying certain conditions,and save computing space to a great extent.At the end of this paper,we have carried out a large number of experimental verifications on the two proposed optimization angles.Experimental results show that the UB-DiWOA algorithm based on the expected up bound proposed in this paper is superior to the existing methods in terms of algorithm accuracy and operating efficiency.