Graph theory defines resilience such that: if graph G has property P, what is the minimum number of edges (E) (links) that need to be removed so that G no longer has P? For example, consider the graph in the Figure on the Left above and its resilience with respect to connectivity. Removing any one edge leaves a connected graph. It is necessary to remove two edges to produce a graph that is not connected (Middle Figure). Thus, we could say that this graph has a resilience of 2 with respect to connectivity. Note that this does not mean that removing any two edges will destroy connectivity in this graph. The Figure on the Right demonstrates the possibility of removing two edges while leaving the graph connected.

Under this definition, a given graph will have different values of resilience with respect to different properties. As a result the definition is concrete but flexible, and can be usefully applied to real-world networks where properties are of variable importance from different perspectives.

The example above highlights the difference between random edge removal and targeted edge removal. If edges are removed randomly, a property might survive the removal of many edges. Targeted edge removal implies that the graph is analyzed and edges are chosen to maximize effect. The effect on the network of either type of edge removal depends in part on degree distribution.

Graphs following a power-law distribution (scale-free) tend to be highly resilient to random edge removal because there is a very good chance that the edges removed will connect only low-degree vertices – and therefore the overall graph structure will be affected only slightly. Graphs are much more vulnerable, however, to targeted removal of edges attached to high-degree nodes, especially to the removal of those nodes themselves. In scale-free graphs, these high-degree vertices are critical in connecting subgraphs.

A graph with a low resilience with respect to a property can lose that property as a result of only a few edge removals. We can say that the graph is vulnerable with respect to that property.

But this is only half of a complete consideration of vulnerability. The other half has to do with the effect on the network’s performance if the property in question has been lost.

In graph theory, resilience is a binary concept: an edge either exists or it does not; a graph either has a property or it does not. In real-world transportation networks, links have additional properties such as capacity, utilization, demand, and cost.

References:

•  This post is adapted from the Wikibook Transportation Geography and Network Science  originally written by the research team.
•  Sudakov, B. and V. H. Vu (2008). Local resilience of graphs. Random Structures & Algo- rithms 33(4), 409–433.
•  Newman, M. E. (2003). The structure and function of complex networks. SIAM review 45 (2), 167–256.