Complex networks, robustness, and attacks

László Barabási’s office is down the hall from my own, and he’s an amazing scientist who works on the statistical mechanics of complex networks. I’ve never heard him speak before yesterday, but at yesterday’s talk he gave a great introduction to complex random and scale-free networks.

In this field, a network is any particular graph that connects nodes with links. The nodes could be power-transmission stations, airports, or web pages, and the links could be power lines, airline routes, or web links. This is a field with implications to everything from biology (proteins and their interactions are a network) to homeland security (terrorists and their cell phone communications are a network).

Yesterday, after hearing László speak about his research, I went and looked up this review article in Reviews of Modern Physics. Some of the conclusions scare me. Some kinds of networks (like the internet) are robust under random node removal, but are fragile under a coordinated “attack” which disables a few highly-connected nodes. We can use this property to our advantage; arrest a Mohammed Atta and a terrorist network may fall to pieces, or find a biochemically important node in HIV transmission and we might be able to stop the disease from propagating. It also points out ways we are vulnerable; if O’Hare airport is attacked, the transportation system in the US may suffer immensely.

The paper is a very interesting read, and is well worth the time spent reading it.