Disintegration Problem Of Complex Network

The rapid development of information technology has promoted the networking process of human society,such as the Internet,the transportation network,the logistics network,the power network,and the trade network.It can be said that we live in a world of network.These networks are often large in scale and complex in structure.They are neither networks with simple rules nor completely random networks,so they are called “complex networks.” Since the discovery of both the small world effects and the scale-free features,complex network research has flourished in the past two decades.In most cases,the networks that we face are ”beneficial”.For these beneficial networks,we hope to ensure their continuous operation through various means,such as optimized design,coordinated control,and defensive repair.Once a node(edge)failed,it will lead to serious consequences.For example,the outages of both the US and Canada power grids caused large-scale power outages in the eight states of US and the two provinces of Canada in August 2003,with economic losses of about 30 billion dollars.In December 2005,the earthquake of the Taiwan Strait caused several international submarine communication cables to be interrupted.The Internet service of the entire Asia-Pacific region is almost inconspicuous.In January 2008,the ice disaster of south China caused traffic congestion,power interruption,water supply stoppage,fuel emergency,and food shortage in more than ten provinces in China.At present,the design of these beneficial networks has always been the focus of attention in many fields,such as management science,information science,applied mathematics,and statistical physics.However,the network which we are facing may also be ”harmful”.The most typical example is the terrorist network.Currently,terrorist organizations have evolved from traditional hierarchical structures to network structures.These terrorist networks usually distribute around the world.How to effectively destroy terrorist networks has become a common problem faced by anti-terrorism organizations around the world.Another typical example is the disease transmission network.In recent years,infectious diseases have become more and more common.How to effectively block the spread of diseases is a daunting task in the field of global public health.These are the problems that need to be faced in the study of complex network disintegration.As one of the most important researches in the complex network,it has become an extremely important and challenging frontier topic.Based on the theory and method of the complex network,this paper uses the knowledge of graph theory,operations research,heuristic algorithm,computer numerical simulation etc.We explore the modeling,analysis,optimization and application of complex network disintegration gradually.The main contents and innovations of this paper are as follows:1.A standard model for the disintegration problem of complex network is given.The study of the disintegration problem of complex network is to determine the set of nodes(edges)whose removal would make the network break down with various constraints and disintegration targets.Actually,its purpose is to find the core of the network system.Therefore,the network disintegration problem can be regarded as a special kind of “key node identification problem”,which is essentially a combinatorial optimization problem.Based on the essence of the above disintegration problem,the basic network model and node removal model of the network disintegration problem are given,along with the evaluation model of the disintegration effect.2.The optimal disintegration strategy of complex networks with key node identification is studied.Network disintegration problem is a special kind of key node identification problem.In this paper,we discuss the network disintegration problem with two research ideas of key node identification.The one is node centrality measure,the other is combinatorial optimization.Firstly,we introduce nine kinds of node centrality measures and discuss the effect and applicability of the disintegration strategies of various centrality measures in depth.Then,we analyze the network disintegration problem based on combinatorial optimization and introduce the heuristic algorithm to solve the objective function of the optimization model.We set the coding,the movement operation,the special criteria,and the termination criterion.The experimental results show that the heuristic algorithm can effectively obtain the approximate optimal solution.The disintegration effect is much higher than the current multi-class measures.The main contribution of this work is to provide an effective research framework and algorithm to seek the disintegration strategy with combinatorial optimization.3.The optimal disintegration strategy for complex networks with the cost constraint model is studied.To analyze the disintegration problem with cost constraint,we define the disintegration cost as the exponential form of the value of the node's centrality measure.A normalized cost constraint model is introduced to define the cost constraint model.The disintegration problem could be adjusted by the cost-sensitive parameter and the cost-constraint parameter.Firstly,three typical disintegration strategies are proposed to compare the corresponding disintegration effects.Then,the genetic algorithm is utilized to seek the optimal disintegration strategy with cost constraint model.Extensive experiments in synthetic networks and real-world networks suggest that the heterogeneity of the disintegration cost and the tightness of the cost constraint significantly affect the optimal disintegration strategy.We demonstrate that,in contrast to the classical hub node strategy,low-cost nodes play a key role in the optimal disintegration strategies if the cost constraint is tight and the disintegration cost is strongly heterogeneous.4.The optimization model for the disintegration strategy in the spatial network is proposed,and an optimization algorithm is introduced to solve the problem.For the current research progress,most studies only pay attention to the network topology and ignore the spatial properties of the network,which leads to the deviation of the experimental results from the real world.Therefore,this paper utilizes the coordinate matrix to cover the spatial information of the network.And the optimization model of disintegration strategy in the spatial network is established with the disintegration circle model and the spatial division mechanism.Then the tabu search with an optimized initial solution is introduced to solve the optimization model,which provides a reasonable and effective research framework.5.Seek optimal disintegration strategies in various types of realworld networks.Seek the optimal disintegration strategies in the background of the Chilean power grid,the terrorist network of the Madrid train bomb,the food chain network of south Florida,the politician blog network,the American airline network,the US fiber network and the Chicago road network.