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

DOI10.1016/j.mbs.2012.07.002zbMath1316.92093WikidataQ38028677 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-hard; epidemics; network reliability; contact network; SIR networks

Mathematics Subject Classification ID

92D30: Epidemiology

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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