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.