The Optimal Disintegration Strategy Based On Tabu Search In Directed Networks

In majority of cases,the networks are benefit,such as power grid,transportation networks,communication networks and logistics networks.For these beneficial network,we hope to keep the stable operation of these networks through designing,coordination control and repairing.In other cases,the networks are harmful such as terrorist networks,rumor networks and epidemic networks.Disintegrating these harmful networks through immune,blockade,isolation and interference has been a challenging problem.The current researches concerning network disintegration strategy are mostly applied on undirected network.However,few researchers have studied the disintegration strategy for directed networks.Therefore,this paper focuses on the optimal disintegration strategy of directed networks.The main contributions are listed as follows:(1)A new method of directed network modeling is proposedThis paper established a random directed network model based on undirected networks by randomly directing a certain proportion of edges in the undirected network.(2)A model of optimal disintegration strategy is establishedWe construct the optimal model of directed network attack strategy by abstracting the problem of disintegration strategy into an optimization problem.In this model,a one-dimensional vector is used for representing whether each node is removed efficiently and effectively.Thus,each disintegration strategy can be presented by a simple one-dimensional vector,which greatly accelerates the algorithm.(3)A disintegration strategy based on tabu search is proposedIn this paper,the tabu search algorithm is introduced to solve the problem of network disintegration.The optimal disintegration strategy of directed network is therefore proposed.It improves the method of judging the importance of nodes or edges by using the local structure feature.Using the efficiency of the intelligent optimization algorithm,it solves the high cost problem of traversing all the disintegration strategies.