Network Robustness

> By Clémence Magnien, Matthieu Latapy and Jean-Loup Guillaume

Network Robustness

Network Robustness

Network robustness is a very important question in many contexts: in communication networks, equipment failures may disrupt the network and prevent users from communicating; in distribution networks (such as power or water distribution), breakdowns can prevent service to customers; also, diseases can spread in contact networks, and vaccinating people (thus in a sense removing them from the network of the disease’s spread) can prevent the infection from reaching a large number of persons.

Many papers have studied this question by considering the size of the largest connected component (i.e. the largest set of nodes such that there exists a path between any two nodes) as a criteria for evaluating the robustness of a network: the larger the size of this component, the larger the number of users who can communicate (or the number of people a disease can infect), and hence the more robust the network.

Most real-world networks have heterogeneous degree distributions (i.e. they have a large number of nodes with small degrees, a small number of nodes with a very high degree, and all intermediate cases), hence studying the robustness of power-law random networks seems relevant. This plot shows the resilience of such a network in face of failures and malevolent attacks. Failures are thought to be random events, and are modeled by random removing of nodes. Attacks aim at disrupting quickly a network, and are modeled by the removal of nodes by decreasing order of their degree. In both cases, the plot shows the fraction of nodes remaining in the largest connected component, as a function of the number of removed nodes.

The behaviors of the network in both cases are very different: while the plot for failures decreases very smoothly and reaches 0 only when almost all nodes have been removed, the plot for attacks decreases very sharply and reaches 0 when only a small fraction of the nodes has been removed. This seems to imply that networks with heterogeneous degree distributions are very resilient to failures, but very fragile against attacks. This would be due to the high degree nodes, which hold the network together. In case of failures, very few of these nodes are removed, and the network resists, but in case of attacks the removal of these nodes disrupts the network very quickly.

The third plot, which shows the effect of almost random attacks, can mitigate this conclusion. These attacks simply consist in removing randomly nodes that have degree at least 2. We can observe that, though it is not as efficient as a classical attack, this strategy succeeds in disrupting the network far more quickly than random failures. This shows that the weakness of networks with heterogeneous degree distributions in face of attacks is also caused by their large number of nodes of degree one.

See this survey for more information.

This entry was posted in Plots and tagged , ,