Attacks on heterogeneous networks

> By Dashun Wang, Albert-László Barabási and Matthieu Latapy

View the high quality movie

Many networks, like for instance the internet, are designed to allow nodes to communicate by sending messages along the links of the network. In others, like social networks, viruses or information spread among nodes by following the links of the network.

In both contexts, the possibility to go from any node to any other in the network, or at least from most nodes to most others, clearly plays a key role. This is captured by the presence of a large connected component.

It was shown in a seminal paper that the heterogeneous distribution of links (some nodes have very few links but others have many) makes them very sensitive to attacks: if one removes nodes by decreasing order of degree (nodes with many links first) then the largest connected component rapidly becomes very small (most nodes cannot communicate with most others anymore).

This movie illustrates exactly this. The size of each node is related to its number of links, and nodes are removed one by one starting with the ones with highest degree. It appears clearly that the network rapidly collapses into a set of small components.

See also this survey, this recent paper, this plot of the week and this movie in the case of an homogeneous network.

This entry was posted in Videos and tagged