Assessing and Increasing Robustness of Networks

Abstract

This thesis aims to assess robustness of networks by evaluating the performance of node attack strategies, the applicability and accuracy of different approaches, and to increase robustness of networks through analysing protecting methods, including link addition and node protection strategies. To be specific, the relative size of the Largest Connected Component (rLCC) and Average Two-Terminal Reliability (ATTR) are chosen to be the performance metrics to evaluate the robustness of networks. In the assessment of network robustness, simulations are employed for ten distinct attack strategies, which include random attack, non-updated and updated degree attacks, non-updated and updated stochastic degree attacks, non-updated and updated betweenness attacks, and greedy attack. Three analytical approximation methods are implemented and discussed, alongside the testing of a machine learning-based approach. Regarding the enhancement of network robustness, the comparative analysis involves thirteen link addition strategies and four node protection strategies. In all node removal scenarios, it is observed that the updated betweenness attack emerges as the most harmful strategy. Moreover, analytical approximations are proved to be effective means of evaluating network robustness in the scenario of predicting robustness for synthetic networks under random attack. Machine learning based methodologies show high accuracy in predicting robustness of synthetic networks, exhibiting acceptable error rates in predicting robustness of real-world networks. Besides, the updated betweenness link addition strategy and targeted betweenness-based node protection exhibit the highest efficacy in protecting networks against the most harmful attacks.