.png){kind=icon}
.png){kind=icon}
Return
Complexity among combinatorial problems from epidemics
.png){kind=icon}
PRE
AI
DOI：10.1111/itor.12444.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A cornerstone in epidemic modeling is the classical susceptible-infected-removed model, or SIR. In this model, individuals are divided into three classes: susceptible (those who can be infected), infected, and removed (those who suffered the infection and recovered, gaining immunity fromfurther contact with infected individuals). Transitions S -> I -> R occur at constant rates gamma(S), gamma(I). The SIR model is both simple and useful to understand cascading failures in a network. Nevertheless, a shortcoming is the unrealistic assumption of random contacts in a fully mixed large population. More realistic models are available from authoritative literature in the field. They consider a graph and an epidemic spread governed by probabilistic rules. In this paper, a combinatorial optimization problem is introduced using graph-theoretic terminology, inspired by an extremal analysis of epidemic modeling. The contributions are threefold. First, a general node immunization problem is defined for node immunization under budget requirements, using probabilistic networks. The goal is to minimize the expected number of deaths under a particular choice of nodes in the system to be immunized. In the second stage, a highly virulent environment leads to a purely combinatorial problem without probabilistic law, called the graph fragmentation problem (GFP). We prove the corresponding decision version for the GFP belongs to the class of NP-complete problems. As a corollary, SIR-based models also belong to this set. Third, a GRASP (greedy randomized adaptive search procedure) heuristic enriched with a path-relinking post-optimization phase is developed for the GFP. Finally, an experimental analysis is carried out under graphs taken from real-life applications.
Keywords:
combinatorial optimization problem
graph fragmentation problem
computational complexity
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K