Abstract


Complex networks are ubiquitous in today’s world, being the infrastructure of modern society. From power grids to transportation highways, network topologies can be found everywhere. As a result, their failure has major consequences on our daily lives, even more so if these problems cascade throughout the network. Therefore, improving the robustness of such networks becomes an essential task, making them able to better cope with occurring failures.

Robustness is defined as the ability of a network to continue performing well when it is subject to attacks and random failures. By representing networks as simple, connected, undirected, weighted graphs, we are able to quantify robustness with the use of some well known topological graph measures. These measures are based on distance, connectivity or centrality. Furthermore spectral measures are also considered.

In addition to surveying these graph measures through experimental evaluation, we also use the distance-based measures in the network robustness improvement process. This process aims at adding a limited number of edges to optimally improve the measures. Although the problem itself is NP-hard, our proposed approximation algorithms can still ensure a good solution. Finally, to demonstrate its applicability, a versatile software tool has been realized which is able to assist in analyzing and improving the robustness of any given network.