Journal club – Immunization and terrorists

I was whiling away some time yesterday when I read this paper [1]. What the paper is about is “effective immunization strategy for scale free networks”. First let me tell you what each of these words mean. If you already know or are not interested, skip to the last two paragraphs.

What is a network? It is a collection of points (nodes) that are connected to each other in some way (links), so that you can get from one point to another though some path along these links. What are the real world systems a network can represent ? The Internet (each computer is a node and each hard wired connection is a link), the world wide web (each website is a node and each link is a link…), social networks of people, biological networks of chemical reactions, epidemiological networks that map out how a disease spreads through a social network of people in physical contact and so on and so forth. In fact, I think there is a subset of mathematicians and physicists who would have you believe that any problem in the world that is worth solving is actually reducible to a question about some property of some network!

What is immunization? It is exactly the same as in English. I give a vaccine to a node (person) so that it cannot be infected by a disease and hence cannot spread it. What is an immunization strategy? Given a network that you do not know much about (only the fact that it is a network) what scheme should I use to immunize nodes so that with least possible immunization I can guarantee that I will not have an epidemic?

And finally, what is a scale free network? You can find some info here, but in my mind, when somebody says scale free network, I imagine airports as nodes and flights that emanate from them as links. Supposing I draw this, it looks like the image alongside [2]. The first thing you notice is that there are hubs. Suppose you close your eyes and pick one point on the network, like as not, that point will be connected to one other point and that point will be a hub, i.e., connected to a whole bunch of other points. You can do this exercise in your mind with airports if you like and you will see the same thing. Mathematically, such networks turn out to have some nice properties, but for the purpose at hand let us leave it at that.

Alright, so much for preliminaries. What is this paper about? Well, it turns out that if you used a “random immunization” strategy, i.e., if you randomly chose a fraction of people that are connected by such a network and immunized them and asked “Is my population now protected from an epidemic?”, you find that you basically have to immunize everybody before you can be sure there is no epidemic. So this is no good as a strategy. So, what is a better strategy? The authors of this paper say that instead of randomly picking people and immunizing them, you do the following. You randomly pick a person, then randomly pick one of his/her acquaintances (a node that is linked to the node you picked) and immunize them instead. In this way, your network becomes protected from epidemics way sooner. This is their primary result [3].

Now if you think about it, it is easy to see why this is true in scale free networks, again using the airports analogy from earlier. Suppose I wanted to shut down air traffic in the USA. I have a list of airports. The way I want to accomplish my mission is by randomly picking airports to shut down. Now suppose I randomly picked an airport and shut down the airport that I picked, it will take me forever to do this for I will choose the hubs with the same probability as I would choose the hundreds of other itty-bitty airports around. Instead if I said I will pick an airport at random and shut down one of the airports it is connected to, I am way more likely to shut down hubs than in my first route. And hence the strategy described in this paper is indeed better for scale free networks.

But what made this paper priceless in terms of amusement obtained for the time spent was the following sentence…”As a final remark, we note that our approach may be relevant to other networks, such as ecological networks of predator prey [32,33], metabolic networks [34], networks of cellular proteins [35], and terrorist networks. For terrorist networks, our findings suggest that an efficient way to disintegrate the network is to focus more on removing individuals whose name is obtained from another member of the network.” Homeland security…are you listening?

Caveats and Disclaimers

[1] I know squat about networks theory, so if you are an expert, correct me and if you are not, do not trust me entirely.

[2] It is actually an image of stock trades in the new york stock exchange stolen from here…thanks to google’s image search, but same difference.

[3] As far as the mathematics go, there are other assumptions in here…the network must a) have a tree structure, b) be undirected, c) uncorrelated, d) unweighted. But for the resolution I have of such things…same difference.