New immunization strategy could halve the doses for stopping computer virus spreading

August 18, 2008 By Lisa Zyga feature

Researchers have developed a new immunization strategy that requires up to 50% fewer immunization doses compared with the current most efficient strategy. The new strategy could be used to prevent the spread of human epidemics and computer viruses, and it applies to a wide variety of networks.

The new method, called the “equal graph partitioning” (EGP) immunization strategy, is being proposed by a team of scientists from Boston University, Bar-Ilan University in Ramat-Gan, Israel, and Stockholm University. Their study is published in a recent issue of Physical Review Letters.

In real life, the number of immunization doses is often limited or very expensive, so a strategy that requires the fewest doses could be very useful. As the researchers explain, the question of how to immunize a network with a minimum number of doses is mathematically equivalent to asking how to fragment a network with a minimum number of node removals.

In this sense, the new EGP strategy works differently than the conventional “targeted strategy.” The main idea of the targeted strategy is to rank the importance of nodes based on how well-connected they are. Then, nodes are removed, starting with those of highest importance, until the network becomes fragmented. In the adaptive targeted strategy, node importance is recalculated after each iteration.

The main idea of the EGP method, on the other hand, is to fragment the network into many connected clusters of equal size. By creating equal-size clusters, doses don’t have to be “wasted” on isolating very small clusters, as in the targeted strategy.

“Disease cannot spread over the boundary of clusters, which means it will be contained in a single cluster,” co-author Yiping Chen of Boston University told “Thus, the best strategy would be making result clusters as small as possible. Among all the clusters, the largest cluster is most important, as most disease occurs here and the spread can be broad. Thus, we need to minimize the size of the largest cluster. Because the total immunization doses are fixed, we have to save shots from small clusters to make the largest one smaller. Intuitively, the best strategy for this is to fragment the network into equal-size clusters.”

The scientists used an algorithm called nested dissection to find the minimum number of nodes to be removed in order to separate a given network into two or more equal-size clusters. The algorithm could also make clusters of an arbitrary size ratio, and then divide the larger cluster again to make equal-size clusters. For example, the algorithm could divide the network into two clusters with size ratio 2:1, and then divide the larger cluster in half.

When comparing the EGP strategy with different strategies, the scientists found that the new strategy exhibited advantages for immunizing all four network models tested.

For instance, in the “workplace network,” which links workplaces when an employee lives in the same household with an employee from a different workplace, the EGP strategy required 15% fewer doses than the second best strategy (the adaptive targeted strategy). This kind of network is often used to model the spreading of influenza, as well as the spreading of information and rumors in society.

In the “autonomous system” network, which describes the Internet network and computer virus spreading, the EGP method required 50% fewer doses than the second best strategies (both the targeted and adaptive targeted strategies performed equally well). The EGP method had similar advantages in fragmenting a network of high energy particle physics citations (23% fewer doses) and a metabolic network describing the interactions between the metabolites of E. coli (20% fewer doses).

For all networks studied, the EGP strategy minimized the infected fraction of the network population by five to ten times compared with the targeted strategy, when using the same number of immunization doses. With these advantages, the scientists hope that the new immunization strategy will benefit populations by taking a more global approach to the prevention of spreading.

“EGP puts every node in consideration with its neighbors, while the targeted strategy only accounts for the individual properties of the nodes,” Chen said of the EGP’s global nature. “For an example, if you already have a network with a loosely connected large cluster and a highly connected small cluster with high degree hubs, EGP will use the rest immunization strength to make the large cluster smaller, while the targeted strategy will get rid of the hubs to make the small cluster even smaller.”

Before implementing the new strategy, the researchers plan to further evaluate its performance in various settings.

“The EGP strategy is a fairly new idea, and currently it is not used in real-world situations yet,” co-author Fredrik Liljeros of Stockholm University said. “Our next step will be to evaluate the strategy in settings where a high proportion of information abort the contact patterns between individuals are known. One possible such setting could, for example, be hospitals where information about the movement of inpatients between wards is registered and stored.”

More information: Chen, Yiping; Paul, Gerald; Havlin, Shlomo; Liljeros, Fredrik; and Stanley, H. Eugene. “Finding a Better Immunization Strategy.” Physical Review Letters 101, 058701 (2008).

Copyright 2008
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of

Explore further: Novel software can recognize eye contact in everyday situations

Related Stories

How plant architectures mimic subway networks

July 26, 2017

It might seem like a tomato plant and a subway system don't have much in common, but both, it turns out, are networks that strive to make similar tradeoffs between cost and performance.

Using miRNA to cure mature B cell neoplasia

August 9, 2017

Almost half of patients with mature B cell neoplasia are faced with the ineffectiveness of existing treatments. However, they may soon benefit from new therapeutic tools relying on miRNA—a small non-coding RNA molecule ...

Mapping how words leap from brain to tongue

June 19, 2017

When you look at a picture of a mug, the neurons that store your memory of what a mug is begin firing. But it's not a pinpoint process; a host of neurons that code for related ideas and items—bowl, coffee, spoon, plate, ...

Recommended for you

ATLAS observes direct evidence of light-by-light scattering

August 15, 2017

Physicists from the ATLAS experiment at CERN have found the first direct evidence of high energy light-by-light scattering, a very rare process in which two photons – particles of light – interact and change direction. ...


Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet Aug 18, 2008
The adaptive targeted strategy is pretty straightforward to implement and works even when information about the network is limited, this new approach on the other hand seems to require almost complete knowledge of the network layout and which makes it pretty hard (if possible at all) to implement reliably in any real world scenario.
not rated yet Aug 18, 2008
so... basically... when a disease comes around, split everyone up into groups. ?
1 / 5 (2) Aug 18, 2008
Statistics rarely prove correct in real world scenarios :-) Especially in smaller groups... Yes humans are creatures of habit but not always.

May be best to keep this to network routing and such.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.