At streets.mn we focus on Minneapolis and Minnesota. We praise what is praise-worthy and condemn what is condemnable. We feel we do it for our own community. And of course we do.

But what we do in Minneapolis is important not just for residents of Minneapolis, rather it matters for residents of the world. You my fellow Minneapolitans (and St. Paulites perhaps), and those in the surrounding environs are residents of communities that should aim to serve as a role model for the rest of the US, and the world, about how cities should function. We are perfecting the Twin Cities not simply for our own benefit, but for that of humanity.

If we fail, people will look to Portland, or Europe, instead. Surely we can do better.

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.

You must be logged in to post a comment.