Source-linked AI summary
Optimal Vaccine Allocation to Control Epidemic Outbreaks in Arbitrary Networks
Victor M. Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, George Pappas
TL;DR
The paper asks how to control epidemics in arbitrary contact networks with heterogeneous individual susceptibility while minimizing vaccination cost. It uses a heterogeneous N-intertwined SIS model, a convex framework for fractional vaccination, and a greedy method for all-or-nothing vaccination, illustrated in a real online social network.
Problem
The problem is to distribute vaccination resources in an arbitrary contact network so an epidemic is controlled at minimum cost.
Method
The paper combines a spectral SIS control condition with convex optimization for fractional vaccination and a greedy approach for all-or-nothing vaccination.
Results
The framework is illustrated in a real online social network, where vaccination costs show a strong dependence on node degree and the reverse greedy algorithm outperforms the compared methods.
Takeaways & Limitations
Vaccination allocation can account jointly for network structure and epidemic parameters rather than relying only on graph-based centrality measures.
Abstract
from arXiv · showhide
We consider the problem of controlling the propagation of an epidemic outbreak in an arbitrary contact network by distributing vaccination resources throughout the network. We analyze a networked version of the Susceptible-Infected-Susceptible (SIS) epidemic model when individuals in the network present different levels of susceptibility to the epidemic. In this context, controlling the spread of an epidemic outbreak can be written as a spectral condition involving the eigenvalues of a matrix that depends on the network structure and the parameters of the model. We study the problem of finding the optimal distribution of vaccines throughout the network to control the spread of an epidemic outbreak. We propose a convex framework to find cost-optimal distribution of vaccination resources when different levels of vaccination are allowed. We also propose a greedy approach with quality guarantees for the case of all-or-nothing vaccination. We illustrate our approaches with numerical simulations in a real social network.
I. INTRODUCTION
The paper studies epidemic control in arbitrary contact networks using a heterogeneous SIS model and vaccination-resource allocation. It develops convex and greedy approaches for fractional and all-or-nothing vaccination.
- Motivation: The study models disease spreading in contact networks where infection rates can differ across individuals.The dynamics depend on network structure, the epidemic model, and individual parameters.
- Motivation: Controlling spreading processes is important in public health and network security.Prior work includes epidemic-threshold analysis, network-specific spreading models, immunization heuristics, and optimization-based control.
- Model and objective: The paper uses a heterogeneous N-intertwined SIS model to formulate vaccination allocation as a network-control problem.Vaccination changes individual infection rates within feasible ranges, with node-dependent costs.
- Model and objective: The objective is to control an initial infection at minimum cost by distributing vaccination resources across the network.The paper considers both fractional vaccination and fully vaccinating selected individuals.
- Spectral control: The control condition is connected to the largest eigenvalue of a matrix determined by the network and epidemic parameters.For the homogeneous model, a spectral stability condition guarantees exponential decay of the infection.
C. Non-Homogeneous N-Intertwined SIS Epidemic Model
The heterogeneous N-intertwined SIS model represents node-specific infection and curing rates through a linear upper-bounding system. Stability of this system provides a sufficient spectral condition for exponential epidemic decay.
- Heterogeneous model: The model assigns each node its own infection rate βi and curing rate δi.The nonlinear epidemic dynamics use diagonal rate matrices and node infection probabilities.
- Linear bound: The nonlinear SIS dynamics are upper-bounded by a linear system with state matrix BAG − D.The upper bound holds for matching initial conditions.
- Stability condition: Stability requires the eigenvalues of BAG − D to lie in the open left half-plane.The matrix has real eigenvalues because it is similar to a symmetric matrix.
- Stability condition: If λ1(BAG − D) < −ε, the infection converges to zero exponentially fast at rate ε.This spectral condition is sufficient to control the epidemic evolution.
III. A CONVEX FRAMEWORK FOR OPTIMAL RESOURCE ALLOCATION
The fractional vaccination problem is formulated as a cost optimization over adjustable node infection rates. Under stronger-than-convexity assumptions on vaccination costs, the resulting framework is tractable.
- Fractional vaccination: Fractional vaccination allows infection rates βi to vary within feasible lower and upper bounds.The bounds represent highly vaccinated and naturally unvaccinated states, respectively.
- Vaccination cost: The cost fi(βi) is node-dependent and represents the resources required to achieve infection rate βi.The paper allows vaccination costs to differ across individuals.
- Vaccination cost: The cost function is decreasing and reaches zero at the natural infection rate and Ti at the minimum infection rate.These properties encode increasing resource requirements for stronger infection-rate reduction.
- Convexity assumptions: Assumption 1 requires twice differentiability and is stronger than ordinary convexity.Because fi is decreasing, the stated condition implies positive second derivative.
- Numerical cost shape: For the illustrated parameter values, the vaccination cost is convex and exhibits diminishing returns.Reducing infection rates requires greater marginal investment in the high-cost range.
B. Problem Statements
The paper defines an optimization problem for distributing vaccines across a network at minimum total cost while enforcing a target exponential decay rate for the epidemic.
- Problem formulation: The problem takes a curing-rate profile and node-specific vaccination cost functions as inputs.The decision concerns vaccine allocation in a given contact network.
- Problem formulation: The objective is to control epidemic propagation with asymptotic exponential decay rate ε at minimum total cost.The formulation follows from the heterogeneous SIS spectral stability condition.
- Solution approach: The paper proposes a convex formulation for solving this optimization problem under Assumption 1.The convexity assumptions make the feasible optimization framework tractable.
C. Semidefinite Programming (SDP) Approach
The paper converts the spectral stability requirement into an equivalent semidefinite constraint, then uses reciprocal infection-rate variables to obtain a convex optimization program for cost-optimal vaccination.
- Spectral reformulation: The condition λ1(BAG −D) ≤−ε is equivalent to the semidefinite constraint (D −εI)B−1 −AG ⪰0.The equivalence relies on the similarity of BAG −D to the symmetric matrix B1/2AGB1/2 −D.
- Convex formulation: The change of variables γi ≜ βi^-1 makes the feasible set convex in the variables γi.The resulting matrix variable is Γ = diag(γi).
- Convex formulation: Under Assumption 1, the vaccination cost function is convex in the transformed variables.The paper verifies this by computing the second derivative and applying Assumption 1.
- Optimization outcome: The convex optimization program efficiently finds the cost-optimal vaccine allocation subject to epidemic-control requirements.The approach is subsequently illustrated in a real social network.
D. Numerical Results
Numerical experiments evaluate vaccination allocation in a 247-node social network under three natural infection-rate levels. Vaccination cost is strongly related to node degree, and higher infection rates increase costs.
- Experimental setup: 247 nodes are used in the social-network simulations, with equal recovery rate δi = δ = 0.1.The experiments compute optimal vaccination distributions for several cases.
- Experimental setup: λ1(AG) = 13.52 and the critical infection rate is βc = δ/λ1(AG) = 7.4e−3.The selected natural infection rates exceed βc, making the disease-free equilibrium unstable without vaccination.
- Experimental setup: The simulations use β̄ ∈ {1.2βc, 1.8βc, 2.4βc}, while full vaccination reduces infection rates to βi = 0.2β̄i.The corresponding minimum rates are {0.24βc, 0.36βc, 0.48βc}.
- Observed allocation patterns: Vaccination cost has an almost affine relationship with node degree, with saturation at the extreme costs 0 and 1.Figure 2 contains 247 points per infection-rate case, plotting node cost against degree.
- Observed allocation patterns: Higher values of β̄ lead to higher vaccination costs because the virus is more infectious.This trend is reported across the simulated infection-rate settings.
IV. COMBINATORIAL RESOURCE ALLOCATION
The combinatorial formulation restricts vaccination to discrete choices, such as fully vaccinating selected individuals. The paper characterizes this problem and develops a greedy approximation with quality guarantees.
- Problem formulation: The combinatorial problem restricts each infection-rate decision to a discrete vaccination-resource set rather than an interval.This contrasts with the fractional formulation, which permits βi values throughout a feasible interval.
- Problem formulation: The goal is minimum total vaccination cost while achieving an asymptotic exponential decay rate ε for the epidemic.The formulation takes curing rates and vaccination cost functions as inputs.
- Problem formulation: An optimal allocation can be represented by the set IC of individuals fully immunized by switching their infection rates from β̄i to βi < β̄i.The paper specializes the cost function so these extreme vaccination choices have costs related to ci.
- Algorithmic treatment: The resulting solution is combinatorial, so the paper proposes a greedy approximation and provides a quality guarantee.The guarantee is developed for the combinatorial solution in the following subsection.
A. Greedy approach
The greedy method builds a vaccination group by selecting nodes according to benefit per unit cost, while a reverse-greedy variant starts with universal vaccination and removes nodes. Both use the spectral control condition.
- Forward greedy algorithm: The greedy algorithm adds the node providing the greatest benefit per unit cost at each iteration.Benefit is defined as the increment in λ1(BStAG −D) induced by vaccinating a node.
- Forward greedy algorithm: The conventional greedy iteration continues until λ1(BStAG −D) ≤−ε, producing a feasible vaccination group.The procedure starts with an empty set and repeatedly adds one node.
- Reverse greedy algorithm: The modified reverse-greedy algorithm starts with all individuals vaccinated and removes nodes according to the smallest removal benefit.It stops when the spectral value reaches the specified boundary and selects the preceding set.
- Quality guarantee: The paper treats the greedy method as heuristic and uses Lagrange duality to provide a quality guarantee.The guarantee addresses the approximation of the combinatorial problem.
B. Quality Guarantee
The greedy approach is evaluated through a Lagrange-dual semidefinite program that supplies an upper bound and an accuracy certificate, despite the absence of strong duality. The dual also provides threshold-based insight into primal vaccination decisions and can reduce the effective dimension of the combinatorial problem.
- Dual-based guarantee: Lagrange duality yields quality guarantees for the greedy approach by computing the dual optimum D*ᶜ.The dual is used to certify greedy performance.
- Dual-based guarantee: The primal optimum can be upper bounded by the dual optimum D*ᶜ computed through Lagrange duality.This bound follows by weak duality.
- Dual-based guarantee: The dual problem is formulated as a standard semidefinite program with a positive-semidefinite domain and epigraph constraints.The formulation follows from decoupling the primal optimization across nodes.
- Dual-based guarantee: Theorem 4.1 provides an accuracy certificate for optimization problems of the stated form by solving the dual problem.The dual solution also gives insight into primal optimizers through threshold solutions.
- Dual-based guarantee: Because strong duality does not hold, the primal and dual optimal values are not expected to coincide or be attainable as equal values.The paper explicitly notes that cᵀb = D*ᶜ is not expected.
- Dual-based guarantee: Threshold information from the dual can fix some nodes’ optimal actions and reduce the dimension of the combinatorial primal problem.Nodes outside the threshold cases may retain actions determined by the dual variables and the associated constraints.
C. Numerical Results
Numerical experiments compare greedy vaccination with degree- and eigenvector-centrality strategies in a 247-node social network. The greedy methods remain close to the dual upper bound, while network-only centrality rankings can miss parameter-dependent optimal choices.
- Algorithm comparison: The greedy algorithms are always within 10% of the upper bound D*ᶜ in the tested parameter settings.The comparison uses three values of the natural infection-rate upper bound and reports objective and residual values.
- Algorithm comparison: The reverse greedy algorithm outperforms the other tested algorithms, especially those based on centrality measures.The comparison includes degree- and eigenvector-centrality strategies.
- Degree analysis: All four algorithms completely vaccinate nodes whose degrees exceed a threshold, but intermediate-degree nodes receive different vaccination decisions.The figure plots degree on a log-scaled horizontal axis against the fraction vaccinated at each degree.
- Degree analysis: Degree alone does not always identify the best vaccination choices.The reported pattern shows that nodes with similar or intermediate degrees cannot be ranked solely by degree.
- Centrality analysis: All four algorithms completely vaccinate nodes with the highest eigenvector centralities, yet lower-centrality nodes can be vaccinated while higher-centrality nodes remain unvaccinated.The cumulative fraction of vaccinated nodes is plotted against eigenvector centrality.
- Centrality analysis: The eigenvectors of δB^-1 − A_G change as vaccinated nodes change, so optimal vaccination depends on β̄ and β as well as network structure.This parameter dependence explains why algorithms based only on graph structure need not produce optimal solutions.
V. CONCLUSIONS
The paper formulates epidemic control in arbitrary contact networks as a spectral optimization problem and develops allocation methods for fractional and combinatorial vaccination. It demonstrates these approaches through simulations in a real online social network.
- Epidemic spread is related to eigenvalues of a matrix determined by network structure and model parameters.
- The control problem is formulated as a spectral optimization problem with semidefinite constraints.
- For fractional vaccination, a convex framework finds optimal vaccine allocations when vaccination-cost functions satisfy certain convexity assumptions.
- For combinatorial vaccination, a greedy approach provides quality guarantees through Lagrangian duality.
- The approaches are illustrated using numerical simulations in a real online social network.