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

August 18th, 2008 By Lisa Zyga

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 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.


print this article email this article download pdf blog this article bookmark this article     Digg this Stumble it share on Facebook share on Reddit add to delicious save to Yahoo! bookmarks
3.9/5 after 23 votes

Rank Filter

Move the slider to adjust rank threshold, so that you can hide some of the comments.



  • superhuman - Aug 18, 2008
    • Rank: not rated yet
    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.
  • Latrosicarius - Aug 18, 2008
    • Rank: not rated yet
    so... basically... when a disease comes around, split everyone up into groups. ?
  • Arikin - Aug 18, 2008
    • Rank: 1 / 5 (2)
    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.
  • JustinDoDrop - Aug 19, 2008
    • Rank: 1 / 5 (1)
    Makes perfect sense to me. Very good strategy.

    RD
    http://www.useurl.us/12m

August 18th, 2008 all stories
Physics / General Physics

Comments: 4
Rank: 3.9/5 after 23 votes

  • Stumble this up

  • Digg this

  • Share it:
  • share on Facebook
  • share on MySpace
  • share on Slashdot
  • rss-newsfeed
  • share on Google
  • share on Reddit
  • add to delicious
  • save to Yahoo! bookmarks
  • share on Windows Live
  • Add to Mixx!
Rating: 3.9/5 after 23 votes

  • Related Stories

  • A Better Shot at Immunization
    created Jul 16, 2008 | popularity not rated yet | comments 0
  • A 'prisoner's dilemma' for real-life situations
    created Sep 20, 2006 | popularity not rated yet | comments 0
  • Zinc-based nano-cages store hydrogen
    created Dec 02, 2005 | popularity not rated yet | comments 0
  • HP Details Strategy to Help Companies Unlock the Value of Stored Data
    created Sep 14, 2004 | popularity not rated yet | comments 0
  • Orion Solves Scientists Problems: Supercomputer on a Desktop
    created Aug 30, 2004 | popularity not rated yet | comments 0


  • Researchers Build World's Largest Disease Association Network
    Researchers Build World's Largest Disease Association Network
    Biology / Other
    created Apr 15, 2009 | popularity 4.6 / 5 (12) | comments 3
  • Quantum Theory May Explain Wishful Thinking
    Quantum Theory May Explain Wishful Thinking
    Medicine & Health / Psychology & Psychiatry
    created Apr 14, 2009 | popularity 4.1 / 5 (41) | comments 13
  • The Physics of Pizza Tossing
    The Physics of Pizza Tossing
    Physics / General Physics
    created Apr 09, 2009 | popularity 3.5 / 5 (11) | comments 7
  • Entangled Light in Bose-Einstein Condensates
    Entangled Light in Bose-Einstein Condensates
    Physics / General Physics
    created Apr 08, 2009 | popularity 4.4 / 5 (15) | comments 8
  • Carbon Nanotubes Toughen a Common Plastic
    Carbon Nanotubes Toughen a Common Plastic
    Nanotechnology / Nanomaterials
    created Apr 07, 2009 | popularity 4.3 / 5 (16) | comments 2
  • Other News

    A step closer to an ultra precise atomic clock

    A step closer to an ultra precise atomic clock

    Physics / General Physics

    created Apr 16, 2009 | popularity 4.8 / 5 (11) | comments 5

    A clock that is so precise that it loses only a second every 300 million years - this is the result of new research in ultra cold atoms. The international collaboration is comprised of researchers from the ...


    Physicists see the cosmos in a coffee cup

    Physicists see the cosmos in a coffee cup

    Physics / General Physics

    created Apr 14, 2009 | popularity 4.6 / 5 (18) | comments 5

    (PhysOrg.com) -- A Duke University professor and his graduate student have discovered a universal principle that unites the curious interplay of light and shadow on the surface of your morning coffee with ...


    Green light from Silicon

    Physics / Condensed Matter

    created Apr 15, 2009 | popularity 4.3 / 5 (12) | comments 4

    (PhysOrg.com) -- Researchers at the University of St Andrews have made a surprise discovery that the material at the heart of the microelectronics industry can emit green light.


    Physicists put a new spin on electrons

    Physics / General Physics

    created Apr 15, 2009 | popularity 4.7 / 5 (12) | comments 4

    In the first demonstration of its kind, researchers at the University of British Columbia have controlled the spin of electrons using a ballistic technique--bouncing electrons through a microscopic channel of precisely constructed, ...


    Scientists demonstrate laser with controlled polarization

    Scientists demonstrate laser with controlled polarization

    Physics / Optics & Photonics

    created Apr 13, 2009 | popularity 3.6 / 5 (13) | comments 3

    Applied scientists at the Harvard School of Engineering and Applied Sciences (SEAS) in collaboration with researchers from Hamamatsu Photonics in Hamamatsu City, Japan, have demonstrated, for the first time, ...