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.