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

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 PhysOrg.com. “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 PhysOrg.com.
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.