Evolutionary Optimization And Theoretical Analysis For Network Robustness

Recently, the research on complex network has been applied to many scientific fields, such as engineering, mathematics, physics, and biology, and it has been attracting many researchers. One of the most significant properties of complex networks is network robustness. Therefore, it is of great importance to know how to enhance the robustness of networks. Many existing literatures numerically and empirically introduced some network robustness measures and used a heuristic algorithm to optimize the network robustness. In this thesis, evolutionary algorithms are used to improve network robustness. And a theoretical analysis is conducted to estimate the value of network robustness measure R, which is proposed by Schneider et al. in [1]. At last, the evolution of network robustness is analyzed under continuous topological changes. The main work is summarized as follows:(1) A new particle swarm optimization(PSO) is proposed to enhance the robustness of scale-free(RSF) networks against malicious node attacks without changing the degree distribution of networks, called PSO_RSF. With the intrinsic properties of the problem of optimizing network robustness in mind, the modified encoding method and updating population operator are designed to improve the ability of global search and local search. Experimental results show that PSO_RSF performs well on scale-free networks with different sizes. The networks after optimization are more robust than original networks and the network structures become “onion-like”.(2) In many practical applications, the constraint of maintaining the degree distribution can be ignored in the robustness optimization problem(ROP). Based on these applications, a new memetic algorithm(MA) is proposed to optimize the robustness of network against malicious node attacks with changing degree distribution, named as MA_ROP. The improved crossover and mutation operators are designed to perform global search, and the heuristic hill-climbing algorithm is employed as the local search operator. The optimization results show that MA_ROP is effective and stable to enhance network robustness. The optimal network topology is closed to regular networks.(3) Schneider et al. in [1] introduced an effective measure R to evaluate the network robustness against malicious attacks on nodes. However, they did not give any theoretical analysis on R. In this thesis, a theoretical method is conducted to calculate the value of R. The study of probability statistics is applied to analyze the effect of malicious attacks. The results show that the theoretical value of R is approximately equal to that of optimized networks and regular networks are more robust than other types of networks, which confirms the above optimized conclusion.(4) Many networks in reality face a dynamic iteration of attacks and defenses, in which attacker and defender take turns to destroy and replenish networks. In this thesis, a modified iterative model is proposed, in which the numbers of nodes and links are kept invariant. Through intensive experiments on several well-known networks, the defense strategy of connecting nodes with low-centrality is effective enough to maintain network connectivity, increase the network robustness R against targeted node attacks, but it cannot enhance the link-robustness R_l against malicious link attacks during the iterative rounds. Significantly, in two real-world networks, this strategy is perfect for simultaneously enhancing the robustness R and the link-robustness R_l.