Research On Critical Node Problem In Network Based On Local Search And Genetic Strategy

With the development of information technology,various kinds of complex networks have emerged,and the identification of key nodes in the network can help understand the network characteristics and maintain the structure and function of the network to a certain extent.The critical node problem is an NP-hard combinatorial optimization problem,and its study has important theoretical and application values.Critical node problem(CNP)involve finding a set of critical nodes from a graph whose removal results in optimizing a predefined measure over the residual graph.Current algorithms for the CNP problem still suffer from high redundancy and insufficient accuracy.Therefore,such algorithms still need further research.In this paper,we focus on CNP2b(also called CC-CNP)among the six types of CNP.The main research contents are as follows.(1)A multistage local search algorithm MSLS is proposed for the CNP2 b problem,which mainly improves the candidate solutions by the "circular deletion" and "node exchange" strategy.In the "node exchange" strategy,we adopt the first-in-first-out(FIFO)principle in Tabu Search.The "circular point deletion" and the FIFO principle in Tabu Search are the two key techniques of this algorithm.The process of "circular point deletion" can reduce the number of nodes in the solution as much as possible.In the process of "node exchange",the point with highest priority in the residual graph is selected to join the current solution by the first-in-first-out principle of the Tabu Search strategy,which can avoid the temporary circuit search and improve the running speed.The experimental results on 16 synthetic networks and 14 real networks show that the Tabu Search strategy could improve the solution's quality and speed up the computation better than randomly selected points;MSLS has better solution quality and faster solution speed on real network graphs than the other two local search algorithms.(2)An algorithm GAMSLS(a genetic algorithm with a multistage local search algorithm for critical node problem,GAMSLS)for the CNP2 problem that combines the Genetic Algorithm(GA)and the local search algorithm MSLS is proposed.The algorithm adopts the GA algorithm framework,used MSLS algorithm to improve the initial solution,followed by a crossover process.We innovatively put the operation of node number reduction in the crossover process and use a new update strategy to better ensure the diversity and quality of individuals in the population.Finally,the effectiveness of GAMSLS algorithm is proved by comparing with the latest benchmark algorithms on three different network graphs.