Apr 27, 2010

The fragility of interdependency

Today, at AALab, we had an interesting discussion about a Nature paper that was published this month: Catastrophic cascade of failures in interdependent networks by Sergey V. Buldyrev, Roni Parshani, Gerald Paul, H. Eugene Stanley  &  Shlomo Havlin

The paper is about surprising characteristics of a failure on two mutually dependent networks. While most existing studies on network robustness have focused on a single network, this doesn't mean that most real networks are independent of each other. Real networks are often mutually dependent, like the power network and the Internet described in the paper. A router cannot function if a nearby power station is out; a power station cannot function if it is disconnected (i.e., if Internet fails). Logical networks like those of financial and political networks are also mutually dependent. Some networks even share the same entities; we belong to multiple social networks like Facebook and Twitter. And when networks are mutually dependent, a single local failure could trigger a disruptive avalanche of cascading and escalating failures. 

Here are three surprising results from the paper:
(Summarized well in Vespignani's article)

1. Networks exhibit a critical threshold value for the fraction of nodes that can be removed above which the network becomes totally fragmented (i.e., the size of the giant component becomes 0). Compared to a single independent network, mutually dependent networks have a much smaller threshold value. This means that mutually dependent networks could collapse at a smaller level of damage.

2. In independent networks, increasing random failures will gradually harm the integrity of the network. However, in mutually dependent networks, increasing random failures lead to abrupt collapse of the network as shown in the graph below. G means the fraction of nodes that belong to the giant connected component. Failures in mutually dependent networks cause a step-like first-order jump around q_c.  

3. In independent networks, heavy-tailed degree distributions have been proven to add great robustness under random failures. Power-law graphs are known more robust to random failures than Erdos-Renyi random graphs. This, however, is also not true in mutually dependent networks. Power-law graphs are more fragile when they are mutually connected. The broader the degree distribution is, the more fragile the networks are.

4 comments:

Juan said...

Mia! Sound like very interesting findings! By any chance you have a copy of the paper? I'm interested to see what they actually mean by "interdependent" (e.g. how failures in one network propagate in the other), and what does it mean for a pair of networks to collapse?

Mia said...

Hi Juan,

Glad to hear that you found the paper interesting. Dependency here means that nodes in the two networks are related so that if a node dies in one network (i.e., power station is out), the other node won't function anymore (i.e., router that gets power from the power station is then out). Cascaded failures will then spread again to the first network (i.e., a power station without the internet connection won't function properly).

You could download the paper here
http://www.nature.com/nature/journal/v464/n7291/abs/nature08932.html

or here
http://arxiv.org/abs/0907.1182

Juan said...

I see.. thanks for the link!

In their results the interdependent pair of networks collapses very quickly because they have a very strong definition of "working network"! They only call a cluster "connected" when their nodes are connected *independently* on each network. So fragmentations in one network cause fragmentations in the other, and this also cascades. That might be true for the power-internet network example, but for something like facebook-twitter this is not the case (i.e. disconnecting users on twitter doesn't mean they can't communicate on facebook). Interdependence in the social graph is actually a good thing, because it adds redundancy to the network!

于呈均名 said...

一棵樹除非在春天開了花,否則難望在秋天結果。......................................................................