Heuristic Algorithms For Scale-free And Interdependent Network Robustness Optimization

In reality,most of the society and nature systems can be represented by networks,such as grid systems,transportation systems,social networks,and communication systems.Most of these systems can be considered as a scale-free network.With the development of science and technology,the current networks are becoming interdependent with each other,and several interdependent single networks constitute an interdependent network.The robustness of networks has been intensively studied in the past decade.Network robustness is the ability of the network to maintain its own system integrity when the network is under attack or failure.Many articles on scale-free networks have proved that scale-free networks are very fragile when they are suffered malicious attacks.It will crash rapidly after the hub nodes are attacked,and the interdependence of nodes will lead failures to other networks,which has serious consequences.Therefore,how to optimize the robustness of the network is a key issue to solve the stability problem.Firstly,this thesis introduces the background of complex networks and the significance of studying network robustness.Then the research status of single-layer network and multilayer network,and some commonly used heuristic algorithms is introduced.Then,this thesis introduces the current mainstream network models and attack strategies,as well as some existing optimization algorithms,including 4 single-layer networks and the interdependent networks coupled with these 4 network models.The attack strategies include degree adaptive attack and the betweenness centrality attack.Then the calculation method of network robustness is given.Then,to ensure the degree distribution unchanging,most of the methods to improve the robustness of the network are random swap edges.Without considering the topology of the network,the performance of existing methods is limited in optimizing the robustness of the network.In this thesis,we proposed a classification method to edges,and a heuristic algorithm for optimizing the robustness of the network is proposed based on this classification method,which is verified in the synthetic networks and the real world networks.The results show that new algorithm outperforms the existing algorithms.Then,this thesis proposed an memetic algorithm for optimizing the robustness of interdependent networks with two local search operators based on the different characteristics of the attack layer and other layers under the malicious attacks.The algorithm has been verified on 7 different types of interdependent networks,and the results show that this algorithm outperforms other algorithms in all models.Then,the theory of the average degree of the adjacent nodes of a k-degree nodes is introduced.Based on this theory,we analyzed the change of interdependent network topology before and after optimization.The attack layer and other layers show the opposite distribution.Finally,we designed an optimization algorithm based on gradient descent for gird networks.An optimal connection rate for each pairs of nodes is designed to represent the influence for network robustness.The gradient descent algorithm updates the optimal connection rate.Finally,an operator is designed based on the optimal connection rate.And a traditional greedy operator is used to achieve fast convergence.The algorithm is finally simulated in the real world network.