Spread of epidemic disease on networks
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsPublished 26 July 2002Open access
M. E. J. Newman
Citations3,285
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
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.
Abstract
The study of social networks, and in particular the spread of disease on networks, has attracted considerable recent attention in the physics community. In this paper, we show 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. In addition to the standard but unrealistic case of fixed infectiveness time and fixed and uncorrelated probability of transmission between all pairs of individuals, we solve cases in which times and probabilities are nonuniform and correlated. We also consider one simple case of an epidemic in a structured population, that of a sexually transmitted disease in a population divided into men and women. We confirm the correctness of our exact solutions with numerical simulations of SIR epidemics on networks.
Keywords
MedicinePhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
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.
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
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.
SIAM ReviewThe Mathematics of Infectious Diseases
6,857 Citations2000Herbert W. Hethcote
Threshold theorems involving the basic reproduction number, the contact number, and the replacement number $R$ are reviewed for classic SIR epidemic and endemic models and results with new expressions for $R_{0}$ are obtained for MSEIR and SEIR endemic models with either continuous age or age groups.
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.
Proceedings of the National Academy of SciencesThe structure of scientific collaboration networks
4,502 Citations2001M. E. J. Newman
It is shown that these collaboration networks form "small worlds," in which randomly chosen pairs of scientists are typically separated by only a short path of intermediate acquaintances.
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
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 topicsRandom graphs with arbitrary degree distributions and their applications
3,644 Citations2001M. E. J. Newman, Steven H. Strogatz +1 more
It is demonstrated that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
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.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
ACM SIGCOMM Computer Communication ReviewOn power-law relationships of the Internet topology
2,599 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
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.
Random Structures and AlgorithmsA critical point for random graphs with a given degree sequence
2,401 Citations1995Michael Molloy, Bruce Reed
It is shown that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if λ0, λ1… which sum to 1, then almost surely all components in such graphs are small.
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.
Transactions of the Royal Society of Tropical Medicine and HygieneInfectious diseases of humans
2,182 Citations1992Adrian Hall
NatureSimple rules yield complex food webs
1,511 Citations2000Richard J. Williams, Neo D. Martinez
This model extends the existing ‘cascade model’ and improves its fit ten-fold by constraining species to consume a contiguous sequence of prey in a one-dimensional trophic niche.
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 topicsSearch in power-law networks
1,207 Citations2001Lada A. Adamic, Rajan M. Lukose +2 more
A number of local search strategies that utilize high degree nodes in power-law graphs and that have costs scaling sublinearly with the size of the graph are introduced and demonstrated on the GNUTELLA peer-to-peer network.
Journal of Combinatorial Theory Series AThe asymptotic number of labeled graphs with given degree sequences
996 Citations1978Edward A. Bender, E. Rodney Canfield
Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: each row sum is specified and bounded, and a specified “sparse” set of entries must be zero.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsEpidemics and percolation in small-world networks
936 Citations2000Cristopher Moore, M. E. J. Newman
The resulting models display epidemic behavior when the infection or transmission probability rises above the threshold for site or bond percolation on the network, and are given exact solutions for the position of this threshold in a variety of cases.
Epidemic outbreaks in complex heterogeneous networks
836 Citations2002Moreno, Y, Pastor Satorras, Romualdo +1 more
Combinatorics Probability ComputingThe Size of the Giant Component of a Random Graph with a Given Degree Sequence
828 Citations1998Michael Molloy, Bruce Reed
The size of the giant component in the former case, and the structure of the graph formed by deleting that component is analyzed, which is basically that of a random graph with n′=n−∣C∣ vertices, and with λ′in′ of them of degree i.
Mathematical BiosciencesOn the critical behavior of the general epidemic process and dynamical percolation
628 Citations1983Peter Grassberger
Journal of Theoretical BiologySmall World Patterns in Food Webs
617 Citations2002José M. Montoya, Ricard V. Solé
The analysis of some species-rich, well-defined food webs shows that they display the so-called small world behavior shared by a number of disparate complex systems, suggesting that communities might be self-organized in a non-random fashion that might have important consequences in their resistance to perturbations.
The Annals of Applied ProbabilityEpidemics with two levels of mixing
546 Citations1997Frank Ball, Denis Mollison +1 more
A general modelling framework for epidemics with removal in populations that mix at two levels: global and local is developed, which allows us to analyze the conditions under which a large outbreak is possible, the size of such outbreaks when they can occur and the implications for vaccination strategies.
Physical Review LettersSmall World Effect in an Epidemiological Model
529 Citations2001Marcelo N. Kuperman, Guillermo Abramson
A model for the spread of an infection is analyzed for different population structures and finds a transition to self-sustained oscillations in the size of the infected subpopulation at a finite value of the disorder of the network.
Mathematical BiosciencesMeasures of concurrency in networks and the spread of infectious disease
421 Citations1996Mirjam Kretzschmar, Martina Morris
Social Science & MedicineSocial networks and infectious disease: The Colorado Springs study
396 Citations1994Alden S. Klovdahl, John J. Potterat +4 more
Overall, for the first time in epidemiologic research a large number of individuals were found connected to each other, directly or indirectly, using a network design.
AIDSNetworks of sexual contacts
307 Citations1989Sunetra Gupta, Roy M. Anderson +1 more
This paper examines the influence of sexual contact patterns (mixing matrices) on the pattern of the AIDS epidemic in a male homosexual community via numerical studies of a mathematical model of the transmission dynamics of HIV with results shown to be assortative and disassortative.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsGiant strongly connected component of directed networks
293 Citations2001S. N. Dorogovt︠s︡ev, J. F. F. Mendes +1 more
It is explained that the giant strongly connected component may be less resilient to random damage than the giant weakly connected one and that the World Wide Web is a directed network.
Journal of the Society for Industrial and Applied MathematicsPercolation Processes and Related Topics
266 Citations1963H. L. Frisch, J. M. Hammersley
This paper is a general review of the current state of the theory of percolation processes and related topics and has attempted to indicate a wide variety of examples drawn from physics, chemistry, biology, engineering, engineering and communication theory of problems which can profitably be considered special instances of a percolations process.
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. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsExact solution of site and bond percolation on small-world networks
178 Citations2000Cristopher Moore, M. E. J. Newman
An exact solution of the model for both site and bond percolation is given, including the position of thePercolation transition at which epidemic behavior sets in, the values of the critical exponents governing this transition, the mean and variance of the distribution of cluster sizes below the transition, and the size of the giant component (epidemic) above the transition.
Mathematical BiosciencesThe spread and persistence of infectious diseases in structured populations
132 Citations1988Lisa Sattenspiel, Carl G. Simon
A stability analysis of the model is presented which shows that there is a unique threshold for disease maintenance, which determines critical subpopulation sizes above which the disease cannot go extinct.
Mathematical BiosciencesA mathematical model for predicting the geographic spread of new infectious agents
127 Citations1988Ira M. Longini
A mathematical model for the temporal and geographic spread of an epidemic in a network of populations is presented and the model is used to predict the spread of Hong Kong influenza in 1968–1969 among 52 of the world's major cities.
AlgorithmicaA Functional Approach to External Graph Algorithms
108 Citations2002Abello, Buchsbaum +1 more
This work presents a new approach for designing external graph algorithms and uses it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spans forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs.
The Journal of Infectious DiseasesAzithromycin Prophylaxis during a Hospital Outbreak of<i>Mycoplasma pneumoniae</i>Pneumonia
50 Citations2001Terri B. Hyde, Mark Gilbert +6 more
Use of azithromycin prophylaxis in asymptomatic persons during an MP outbreak in a closed setting may be of value in reducing clinical illness.
arXiv (Cornell University)Firewalls, Disorder, and Percolation in Epidemics
10 Citations2001Christopher P. Warren, L. M. Sander +1 more
A spatial model related to bond percolation for the spread of a disease that includes variation in the susceptibility to infection is considered, qualitatively different from those of standard models in epidemiology, but correspond to real effects.