Structural Vulnerability Measures for Networks and Graphs

Networks appear in many different applications and settings, the more known ones being telecommunication networks, computer networks, the internet, road and rail networks, and other logistic networks, like gas and electricity networks. In all applications of networks vulnerability and reliability are crucial and important features. From a practical point of view, in many network applications the first thing one wants to know is how well the network performs with regard to node or link failures: are the remaining nodes still connected if some of the nodes or links break down? This is captured by the concepts of connectivity and edge connectivity that are well-studied within the research area of graph theory. Due to existing knowledge from this area the level of connectivity and edge connectivity is closely related to the existence of certain sets of nodes and links that separate the network in disconnected parts, as well as to the existence of certain connecting paths between pairs of nodes. These structural results have very nice algorithmic implications, namely that the level of connectivity and edge connectivity, as well as the connecting paths between pairs of nodes can be determined by fast algorithms. So at first sight everything seems to be satisfactorily settled. However, in practice the measures connectivity and edge connectivity are too simple and too rude: they do not capture the effect of node or link failures on networks well enough. Depending on the type of application, one would like to take into account other effects of node or link failure (vertex or edge deletions), like the number of resulting components, the size of the largest (smallest) component, a split in (almost) equally sized parts, etc. In the proposed research we study various vulnerability measures that capture such effects. We will develop and extend the knowledge base for these measures by analysing their structural properties. We will also consider algorithmic aspects that will help us in answering the question how easy or difficult these measures can be computed in (large) networks. These structural and algorithmic properties of vulnerability measures can also have an impact on solving other difficult optimization problems for networks. If one can break a large network into smaller networks by deleting certain sets of nodes or links, then under some conditions the solutions for the optimization problem on the smaller networks can be combined to a solution for the optimization problem on the larger network. This approach for solving optimization problems is known as divide-and-conquer.