Optimal Attack Strategy Of Complex Networks

With the rapid development of information technology,the human society entered the network era since entering the 21 st century.Networks such as Internet,telecommunications networks,power grids,transportation networks,and a variety of social networks,logistics network are become gradual expansion of the size,more complex of the structure and increasingly powerful of the function,it can be said that our lives are surrounded by various networks.However,except for the convenience they bring to human life,they produce a series of serious problems.In major cases,networks are beneficial,including examples like the Internet,the power-grids and the transportation,which we need to maximize their function.Over the past decade,the outbreak and spread of virus like SARS,H1N1 and Ebola is more frequent and difficult to control;the sabotage of the terrorists is more rampant after 9/11.We want to minimum those networks with harmful function,such as epidemic spreading networks,terrorist networks through immunization,disturbances,collapse and other means to destroy its network structure,so that the network function is not working properly.Thus,the study of network disintegration has a broad application background.From random failure,intentional attack to disintegration based on incomplete information,as a focus,the study of disintegration model for complex networks is increasingly of great theoretical significance and application importance as an challenging topics of complex network theory.In this paper,guided by complex network and optimization algorithm theory and regarding the less attention,we introduce the tabu search and unequal probability sampling into the network disintegration problem with different cost model.Using methods of statistical physics,graph theory,matrix theory,operation research,game theory,probability theory,mathematical statistics and computer simulation,we present an optimized attack strategy model for different attack cost.The main results and contributions of this dissertation are as follows:(1)Introduce a new connected component algorithm for the experiments of complex network disintegration.This paper presents a new form of graph contraction referred to as the “hub contraction”.Based on the hub contraction principle,we propose a fast connected component algorithm,The results showed the performance of our algorithm to be superior in terms of the processing time it requires,most notably when applied to scale-free networks.(2)Introduce tabu search into the problem of complex network disintegration with homogeneous cost.The problem of network disintegration has broad applications and recently has received growing attention,such as network confrontation and disintegration of harmful networks.This paper presents an optimized attack strategy model for complex networks and introduces the tabu search into the network disintegration problem to identify the optimal attack strategy,which is a heuristic optimization algorithm and rarely applied to the study of network robustness.The efficiency of the proposed solution was verified by comparing it with other attack strategies used in various model networks and real-world network.Numerical experiments suggest that our solution can improve the effect of network disintegration and that the “ best ” choice for node failure attacks can be identified through global searches.Our understanding of the optimal attack strategy may also shed light on a new property of the nodes within network disintegration and deserves additional study.(3)Introduce unequal probability sampling into the problem of complex network disintegration with heterogeneous cost.The problem of network disintegration,such as suppressing the epidemic spreading and destabilizing terrorist networks,has broad applications and recently has received growing attention.This paper first presents a limited cost model of attack strategy on complex networks,and the network performance is quantitatively measured by the size of the largest connected component.Here,we introduce the unequal probability sampling into the network disintegration problem to identify the optimal attack strategy,in which node coding is proposed.The efficiency of the proposed solution was verified by applying in model network and real-world network.Numerical experiments suggest that our solution can sift the optimal attack strategy regarding the attack cost.We get some insightful conclusions about the relationship between attack cost and the optimal attack strategy.We find that the low-degree nodes are attacked preferentially when the total cost is deficient;moreover,the high-degree nodes are attacked preferentially when the total cost is sufficient.However,there is a climax,the high-degree nodes won't be attacked preferentially if the cost of single node is more than a threshold.We believe our understanding will be helpful to decision-maker.(4)The optimal attack strategy for real-world network is investigated.We use the American grid,Madrid train bomb terrorist network and Jazz singers relationship network as the background.With important defense establishment and relationships between the characters as a modeling perspective,we use the software Gephi to draw the three real-world network.Then we analyze the effect of the model and the optimization algorithm on the target network.Studies show that our optimal attack strategies perform excellently both in the real-world networks and model networks.