Structural Vulnerability Measures for Networks and Graphs
Lead Research Organisation:
Durham University
Department Name: Engineering and Computing Sciences
Abstract
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.
Organisations
Publications
Broersma H
(2009)
Combinatorial Algorithms
BirĂ³ P
(2011)
Computing solutions for matching games
in International Journal of Game Theory
Bauer D
(2012)
Toughness and Vertex Degrees
in Journal of Graph Theory
Golovach P
(2012)
Containment relations in split graphs
in Discrete Applied Mathematics
Golovach P
(2012)
Algorithms - ESA 2012
Vernitski A
(2012)
Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions
in Journal of Discrete Algorithms
Couturier J
(2012)
Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds
in Theory of Computing Systems
Bonamy M
(2012)
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
in Journal of Combinatorial Optimization
Bonsma P
(2012)
The complexity of finding uniform sparsest cuts in various graph classes
in Journal of Discrete Algorithms
Johnson M
(2013)
Obtaining Online Ecological Colourings by Generalizing First-Fit
in Theory of Computing Systems
Golovach P
(2013)
Modifying a Graph Using Vertex Elimination
in Algorithmica
Johnson M
(2013)
Algorithms and Computation
Patel V
(2013)
Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
in SIAM Journal on Computing
Broersma H
(2013)
Fully decomposable split graphs
in European Journal of Combinatorics
Pyatkin A
(2013)
Triangle-free 2 P 3 -free graphs are 4-colorable
in Discrete Mathematics
Broersma H
(2013)
On Toughness and Hamiltonicity of 2 K 2 -Free Graphs
in Journal of Graph Theory
Belmonte R
(2013)
Characterizing graphs of small carving-width
in Discrete Applied Mathematics
Golovach P
(2014)
Lift-contractions
in European Journal of Combinatorics
Broersma H
(2014)
Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
in Journal of Graph Theory
Chalopin J
(2014)
Packing bipartite graphs with covers of complete bipartite graphs
in Discrete Applied Mathematics
Martin B
(2015)
The computational complexity of disconnected cut and 2 K 2 -partition
in Journal of Combinatorial Theory, Series B
Kang R
(2015)
A Precise Threshold for Quasi-Ramsey Numbers
in SIAM Journal on Discrete Mathematics
Description | Networks (also called graphs) 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. Our objectives were to obtain new structural and complexity results related to vulnerability measures. In particular we researched special graph classes and determined which choice of vulnerability measure was the most appropriate. One of the main findings in the project was that for the class of interval graphs the so-called scattering number is better suitable for determining hamilton-connectivity (a well-known connectivity measure) than the toughness of a graph, the best-known vulnerability measure. Roughly speaking, instead of taking the smallest ratio of the number of vertices in a set and the number of connected components in the subgraph on the remaining vertices, we showed that for interval graphs it is more appropriate to consider the maximum absolute difference between these two numbers. Besides showing a structural characterization of interval graphs in terms of their scattering number, this also resulted in a fast algorithm for computing the hamilton-connectivity of an interval graph. |
Exploitation Route | This is fundamental research which was, as mentioned in the original grant application, mainly of interest to researchers working in Theoretical Computer Science and Discrete Mathematics. |
Sectors | Digital/Communication/Information Technologies (including Software) |