Finding the probability of infection in an SIR network is NP-hard

DOI10.1016/j.mbs.2012.07.002zbMath1316.92093OpenAlexW2027314599WikidataQ38028677 ScholiaQ38028677MaRDI QIDQ1926503

Yanyan Li

Publication date: 28 December 2012

Published in: Mathematical Biosciences (Search for Journal in Brave)

Full work available at URL: http://europepmc.org/articles/pmc3478503

zbMATH Keywords

NP-hardepidemicsnetwork reliabilitycontact networkSIR networks

Mathematics Subject Classification ID

Epidemiology (92D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Stochastic descriptors in an SIR epidemic model for heterogeneous individuals in small networks ⋮ A covering-graph approach to epidemics on SIS and SIS-like networks ⋮ Approximating individual risk of infection in a Markov chain epidemic network model with a deterministic system

Cites Work

• On the critical behavior of the general epidemic process and dynamical percolation
• SIR dynamics in random networks with heterogeneous connectivity
• Some elementary properties of SIR networks or, Can I get sick because you got vaccinated?
• Pandemic simulation of antivirals+school closures: buying time until strain-specific vaccine is available
• Computational complexity of impact size estimation for spreading processes on networks
• Percolation on heterogeneous networks as a model for epidemics
• Scalable influence maximization for independent cascade model in large-scale social networks
• Predicting epidemics on directed contact networks
• The cross-entropy method for network reliability estimation
• The implications of network structure for epidemic dynamics
• A Monte Carlo Sampling Plan for Estimating Network Reliability
• A Survey of Network Reliability and Domination Theory
• Contact network epidemiology: Bond percolation applied to infectious disease prediction and control
• Complexity of network reliability computations
• Computing the Reliability of Complex Networks
• Computing Network Reliability
• The Structure and Function of Complex Networks
• THE TREE CUT AND MERGE ALGORITHM FOR ESTIMATION OF NETWORK RELIABILITY
• Collective dynamics of ‘small-world’ networks
• Algorithms – ESA 2005
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding the probability of infection in an SIR network is NP-hard