Analysis And Research Of Network Robustness Based On Optimization Algorithms

In recent years,the research on complex network has prompted extensive attention.A vast number of infrastructures in real life can be modeled as complex networks,such as power supply network,traffic network,Internet and so on.Most of complex networks are not random but embodied in a kind of special structure.The scale-free network is a special form of the complex network,where there are a few important nodes that hold a dominant proportion of connections,and new added nodes will be connected to these influential nodes with a high probability.The scale-free network has the "heavy-tail" characteristic and thus becomes extremely fragile,which makes it inevitable to break down in a diverse way.Network robustness is an index used to evaluate the resistance of a network to various attacks.In recent years,many optimization algorithms have been used to tackle this problem,such as simulated annealing algorithm,memetic algorithm,tabu search algorithm and so on.Nonetheless,all of these algorithms are insufficient to achieve satisfactory results in improving the network robustness.We study the problem in this thesis,and main purposes and contributions of our research are as follows:(1)Because the robustness optimization problem of networks is known to be NP-complete,researchers always expect to find new meta-heuristic algorithms to improve the robustness of networks as much as possible.In this thesis,an improved algorithm based on Iterated Local Search(ILS)is proposed to optimize the robustness of scale-free networks and improve their resistance to node-based malicious attacks.Furthermore,this thesis has optimized the existing node robustness metrics so that it can characterize the two extreme networks,the star-like network,and the fully connected network more accurately.The ILS algorithm seeks a suboptimal solution as terrific as possible through iterative local search and perturbation operations.In the local search stage,the algorithm adds a constraint condition that is more in line with the "onion-like" characteristic of the optimized network to reduce the computation amount.And in the perturbation stage,the operators adopted by the algorithm differ from those in the local search stage.Experimental results on artificial scale-free networks and real-world networks indicate that,compared with the existing several optimization algorithms,the ILS algorithm can converge to a better solution in less time.(2)In addition to attacking the important nodes,malicious attacks also tend to do damage to other crucial components of the network in the real world.And in many cases a variety of attack modes are simultaneous.Therefore,considering this situation,this thesis makes further step to model the robust-improvement problem in scale-free network as a multi-objective optimization problem.And we make a discussion on how to improve the robustness of scale-free networks when facing malicious attacks against influential nodes and edges at the same time.Firstly,the existing edge robustness metric is optimized in this thesis,and the multi-objective optimization problem is transformed into a single-objective optimization problem by a weighted summation of the edge robustness metric and the node robustness metric.Then the ILS algorithm is used to optimize the scale-free network under the hybrid attack model,and the influence on the network robustness is studied by changing the weighting coefficient.Experimental results on artificial networks and real-world networks show that the scale-free network robustness optimization algorithm based on ILS can converge to a better-quality solution compared with other optimization algorithms.Besides,this thesis compares the optimized scale-free network topology under three attack models:node malicious attack,edge malicious attack,and hybrid attack.It is found that the optimized scale-free network topology under the hybrid attack model is an intermediate one between the initial network and the "onion-like" structure.