Efficient Immunization Strategies for Computer Networks and Populations
Physical Review LettersPublished 9 December 2003Open access
Reuven Cohen, Shlomo Havlin, Daniel ben‐Avraham
Citations1,160
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the immunization threshold is dramatically reduced with the suggested strategy, for all studied cases, and analytically the critical threshold for complete immunization is studied.
Abstract
We present an effective immunization strategy for computer networks and populations with broad and, in particular, scale-free degree distributions. The proposed strategy, acquaintance immunization, calls for the immunization of random acquaintances of random nodes (individuals). The strategy requires no knowledge of the node degrees or any other global knowledge, as do targeted immunization strategies. We study analytically the critical threshold for complete immunization. We also study the strategy with respect to the susceptible-infected-removed epidemiological model. We show that the immunization threshold is dramatically reduced with the suggested strategy, for all studied cases.
Keywords
Social SciencesEnvironmental SciencePhysics and Astronomy
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
NatureExploring complex networks
8,339 Citations2001Steven H. Strogatz
This work aims to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture.
Annals of Internal MedicineInfectious Diseases of Humans: Dynamics and Control
8,011 Citations1992
This book discusses the biology of host-microparasite associations, dynamics of acquired immunity heterogeneity within the human community indirectly transmitted helminths, and the ecology and genetics of hosts' parasites, genetic variability, and drug resistance.
NatureError and attack tolerance of complex networks
7,218 Citations2000Réka Albert, Hawoong Jeong +1 more
It is found that scale-free networks, which include the World-Wide Web, the Internet, social networks and cells, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates.
Physical Review LettersEpidemic Spreading in Scale-Free Networks
5,770 Citations2001Romualdo Pastor‐Satorras, Alessandro Vespignani
A dynamical model for the spreading of infections on scale-free networks is defined, finding the absence of an epidemic threshold and its associated critical behavior and this new epidemiological framework rationalizes data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks.
NatureLethality and centrality in protein networks
5,398 Citations2001Hawoong Jeong, S. P. Mason +2 more
It is demonstrated that the phenotypic consequence of a single gene deletion in the yeast Saccharomyces cerevisiae is affected to a large extent by the topological position of its protein product in the complex hierarchical web of molecular interactions.
Physical Review LettersAssortative Mixing in Networks
4,980 Citations2002M. E. J. Newman
This work proposes a model of an assortatively mixed network and finds that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.
NatureThe large-scale organization of metabolic networks
4,031 Citations2000H. Jeong, B. Tombor +3 more
This analysis of metabolic networks of 43 organisms representing all three domains of life shows that, despite significant variation in their individual constituents and pathways, these metabolic networks have the same topological scaling properties and show striking similarities to the inherent organization of complex non-biological systems.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpread of epidemic disease on networks
3,285 Citations2002M. E. J. Newman
This paper shows that a large class of standard epidemiological models, the so-called susceptible/infective/removed (SIR) models can be solved exactly on a wide variety of networks.
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
Proceedings of the National Academy of SciencesClasses of small-world networks
3,086 Citations2000Luı́s A. Nunes Amaral, Antonio Scala +2 more
Evidence of the occurrence of three classes of small-world networks, characterized by a vertex connectivity distribution that decays as a power law law, and the nature of such constraints may be the controlling factor for the emergence of different classes of networks are presented.
Physical Review LettersNetwork Robustness and Fragility: Percolation on Random Graphs
2,422 Citations2000Duncan S. Callaway, M. E. J. Newman +2 more
This paper studies percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolators, bond percolations, and models in which occupation probabilities depend on vertex degree.
Physical Review LettersResilience of the Internet to Random Breakdowns
2,327 Citations2000Reuven Cohen, Keren Erez +2 more
This work shows analytically and numerically that for alpha0.99.
Physica A Statistical Mechanics and its ApplicationsEvolution of the social network of scientific collaborations
2,102 Citations2002A.L Barabási, H Jeong +4 more
The results indicate that the co-authorship network of scientists is scale-free, and that the network evolution is governed by preferential attachment, affecting both internal and external links, and a simple model is proposed that captures the network's time evolution.
Physical Review LettersBreakdown of the Internet under Intentional Attack
1,423 Citations2001Reuven Cohen, Keren Erez +2 more
It is argued that, near criticality, the average distance between sites in the spanning (largest) cluster scales with its mass, M, as square root of [M], rather than as log (k)M, as expected for random networks away from criticality.
Proceedings of the National Academy of SciencesRandom graph models of social networks
1,363 Citations2002M. E. J. Newman, Duncan J. Watts +1 more
It is found that in some cases, the models are in remarkable agreement with the data, whereas in others the agreement is poorer, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
NatureThe web of human sexual contacts
1,318 Citations2001Fredrik Liljeros, Christofer R. Edling +3 more
Promiscuous individuals are the vulnerable nodes to target in safe-sex campaigns.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsImmunization of complex networks
1,270 Citations2002Romualdo Pastor‐Satorras, Alessandro Vespignani
It is shown that the random uniform immunization of individuals does not lead to the eradication of infections in all complex networks, and networks with scale-free properties do not acquire global immunity from major epidemic outbreaks even in the presence of unrealistically high densities of randomly immunized individuals.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsScale-free topology of e-mail networks
952 Citations2002Holger Ebel, Lutz-Ingo Mielsch +1 more
The resulting network exhibits a scale-free link distribution and pronounced small-world behavior, as observed in other social networks, implying that the spreading of e-mail viruses is greatly facilitated in real e- mail networks compared to random architectures.
Proceedings of the Royal Society B Biological SciencesComplexity and fragility in ecological networks
804 Citations2001Ricard V. Solé, José M. Montoya
The results suggest that ecological networks are very robust against random removals but can be extremely fragile when selective attacks are used, and have important consequences for biodiversity dynamics and conservation issues, current estimations of extinction rates and the relevance and definition of keystone species.
Proceedings of the National Academy of SciencesModeling the Internet's large-scale topology
677 Citations2002Soon‐Hyung Yook, Hawoong Jeong +1 more
This work identifies the universal mechanisms that shape the Internet's router and autonomous system level topology and finds that the physical layout of nodes form a fractal set, determined by population density patterns around the globe.
Mathematical BiosciencesOn the critical behavior of the general epidemic process and dynamical percolation
628 Citations1983Peter Grassberger
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsHalting viruses in scale-free networks
602 Citations2002Zoltán Dezső, Albert-Ĺaszló Barabási
It is demonstrated that policies that discriminate between the nodes, curing mostly the highly connected nodes, can restore a finite epidemic threshold and potentially eradicate a virus.
American Journal of SociologyWhy Your Friends Have More Friends Than You Do
586 Citations1991Scott L. Feld
Physical Review LettersRobust Patterns in Food Web Structure
304 Citations2002J. Camacho, Roger Guimerà +1 more
It is found that several quantities characterizing these diverse food webs obey functional forms that are universal across the different environments considered and suggest that statistical physics concepts such as scaling and universality may be useful in the description of ecosystems.
Mathematical BiosciencesEpidemiological models for heterogeneous populations: proportionate mixing, parameter estimation, and immunization programs
286 Citations1987Herbert W. Hethcote, James W. Van Ark
Social NetworksEgo-centered networks and the ripple effect
286 Citations2003M. E. J. Newman
This work argues that oneOs acquaintances, oneOs immediate neighbors in the acquaintance network, are far from being a random sample of the population, and that this biases the numbers of neighbors two and more steps away, and presents an improved theoretical model which gives significantly better results.
Mathematical BiosciencesSpatial heterogeneity and the design of immunization programs
247 Citations1984Robert M. May, Roy M. Anderson
An optimum eradication program is defined as that which—treating different groups differently—achieves its aim by immunizing the smallest overall number in each cohort of newborns, and it is shown this optimum program requires fewer immunizations than would be estimated under the (false) assumption that the population is homogeneously mixed.
Mathematical BiosciencesPercolation on heterogeneous networks as a model for epidemics
216 Citations2002Leonard M. Sander, Christopher P. Warren +3 more
It is suggested that heterogeneity in the epidemic will affect the phylogenetic distance distribution of the disease-causing organisms and the small world lattices are investigated, and the effects are even stronger.
Physical Review LettersScale-Free Networks on Lattices
178 Citations2002Alejandro Rozenfeld, Reuven Cohen +2 more
It is found that all networks with lambda>2 can be successfully embedded up to a (Euclidean) distance xi which can be made as large as desired upon the changing of an external parameter.