Transportation Geography and Network Science/Resilience

From Wikibooks, open books for an open world
Jump to: navigation, search

Resilience in Graph Theory[edit]

Definition[edit]

Sudakov and Vu (2008)[1] have proposed the most concrete definition of resilience in graph theory: if graph G has property P, what is the minimum number of edges that need to be removed so that G no longer has P?[2] For example, consider the graph in figure 1 and its resilience with respect to connectivity. Removing any one edge leaves a graph that is still connected. It is necessary to remove two edges to produce a graph that is not connected (figure 2). 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. Figure 3 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.

Some discussions of resilience focus on vertex removal rather than edge removal. The effect of removing a vertex on the rest of the network is equivalent to the effect of removing all edges attached to that vertex.

Edge Removal Methods: Random and Targeted[edit]

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 which will achieve the minimum. [3]

Resilience of Scale-Free Graphs[edit]

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. They are much more vulnerable, however, to targeted removal of edges attached to high-degree nodes, and especially to the removal of those nodes themselves. In scale-free graphs, these high-degree vertices are critical in connecting subgraphs.[3]

Resilience and Vulnerability[edit]

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 part 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, and is discussed under Transportation Geography and Network Science/Reliability.

Resilience of Transportation Networks[edit]

Figure 4

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 and cost. We can apply the concepts of resilience to transportation networks by considering the effects of changes in link properties on properties of the overall network.

Figure 5

For example, consider the network in figure 4, where the nodes represent cities and the links represent freight rail lines. Each link has a cost representing the time required to traverse it, in hours. It is a property of the network that there exists a path from A to D whose total cost is 10 hours or less. Now imagine some event occurs which increases the cost of the A-D link by 50%, to 15. The exact nature of the event is irrelevant; it could be a snowstorm, fatigued rails, or a government-imposed speed limit. This event was sufficient to destroy the network’s property of having an A-D path of cost 10 or less.

However, it did not destroy the network’s property of connectivity; A and D are still connected (though at a higher path cost). When evaluating the resiliency of a transportation network, it is important to keep in mind that the network will have different levels of resiliency with respect to different properties.

Improving Resilience[edit]

Once a network’s resilience with respect to a certain property has been evaluated, it is often desirable to improve the resilience. This can be achieved in two fundamental ways: by adding redundancy or by over-provisioning existing links. (Bell 2000, Intro)

Redundancy[edit]

Imagine that we could reduce the cost of links A-B and C-D from 8 to 6, as shown in figure 5. This improved network has three node-independent paths from A to D of cost 10 or less. If the same event happens to this network, the property will not be destroyed. Destroying the same property in the improved network requires more changes that it did in the original network. Therefore we can say that the improved network is more resilient with respect to this property.

Over-provisioning[edit]

A link is over-provisioned if it has more capacity than needed to handle normal levels of traffic. This "reserve capacity" can help the link, and therefore the overall network, maintain adequate levels of performance when link capacity is degraded. Capacity will still be reduced, but may remain able to provide a desired level of service. In our example, we can represent over-provisioning by upgrading the A-D link so that its initial cost is 6. The same event increasing its cost by 50% will now result in a cost of 9 hours — still less than the desired service level of 10 hours.


References[edit]

  1. Sudakov and Vu 2008,"Local Resilience of Graphs". http://www.math.ucla.edu/~bsudakov/resilience.pdf
  2. Sudakov 2008
  3. a b Newman 2003