Research Of The Critical Node Detection Problem Based On The Local Characteristic Of Network

The complex network is widespread in nature,such as social networks,biological networks,power networks and etc.The nodes that have important impacts on network connectivity are often known as critical nodes and the removal of these nodes would significantly degrade network connectivity.While the CNDP(critical node detection problem,CNDP)is the optimization problem that consists in finding the set of the critical nodes that has greatest impact on network connectivity under specific condition.In addition,identifying critical nodes is an efficient way to analyze and apprehend the properties,structures,and functions of networks.This paper studies the critical nodes identification based on the local characteristics of networks.The main work includes:(1)An algorithm GCNP(greedy algorithm for critical node problem,GCNP),is proposed based on the centrality of nodes.Firstly,the GCNP selects nodes according to a kind of centrality measure,such as degree,betweenness,Local Rank and so on,to obtain a vertex cover of the interesting network.A residual graph is obtained after deleting the vertex cover set from the network.Since the size of selected vertex cover set is always larger than the preset size of critical node set.Then,GCNP would choose nodes greedily from the vertex cover to add back to the residual network iteratively,until the number of remaining nodes satisfies preset size of critical node set.The node whose replacement would lead to minimum increment of the pairwise connectivity in the residual graph would be put back first.In addition,a centrality measure LNC(local neighbor centrality,LNC)based on local topological characteristics is defined to better select nodes of initial vertex cover.Experiment results on 16 artificial networks and 9 real networks show that the proposed algorithm framework GCNP could improve the performance of some classical centrality measures for identifying critical nodes in a complex network;The proposed centrality measure LNC is more effective in evaluating the importance of nodes compared with other centrality measures;And the LNC under GCNP performs better than other centrality measures.(2)An algorithm CNOA(critial nodes optimization method,CNOA)is proposed based on the ILS(iterative local search,ILS)framework for identifying critical nodes in network.The iterative optimization process and random perturbation process are used to optimize the critical nodes and improve the quality of the solution.The node in large connected components is selected to exchange with node of feasible solution and the weighting strategy assigns weights to nodes to avoid the frequent exchange of some nodes in the process of iterative optimization.Meanwhile,the random pertuation strategy randomly selects some nodes from union nodes of large connected components to perturb the current solution and the critical nodes of high-quality can be obtained after iterative optimization based on the perturbation solution.The effectiveness of iterative optimization and random perturbation is verified.The simulation experiments on 16 artificial networks and 14 real networks show that the iterative optimization process and random perturbation strategy of CNOA can effectively improve the quality of feasible solution and identify the critical nodes more accurately on most networks compared with other 4 heuristic algorithms.