Source-linked AI summary
Optimal Resource Allocation for Network Protection Against Spreading Processes
Victor M. Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, George Pappas
TL;DR
The paper asks how to contain spreading processes in arbitrary directed networks by allocating costly preventive and corrective resources. It formulates rate- and budget-constrained allocations using geometric programming and applies the framework to an air-transportation epidemic network. The resulting strategies are polynomial-time computable and exhibit nontrivial resource patterns not generally captured by simple centrality heuristics.
Problem
The paper studies how to distribute costly preventive and corrective resources through directed networks to control spreading processes under rate or budget constraints.
Method
The paper uses geometric programming to jointly optimize preventive and corrective resources in weighted, directed networks with nonidentical agents and node-dependent costs.
Results
The allocation framework solves both resource-allocation problems in polynomial time and produces nontrivial protection patterns in an air-transportation network.
Takeaways & Limitations
Optimal protection strategies need not follow simple heuristics based on traditional network centrality measures.
Abstract
from arXiv · showhide
We study the problem of containing spreading processes in arbitrary directed networks by distributing protection resources throughout the nodes of the network. We consider two types of protection resources are available: (i) Preventive resources able to defend nodes against the spreading (such as vaccines in a viral infection process), and (ii) corrective resources able to neutralize the spreading after it has reached a node (such as antidotes). We assume that both preventive and corrective resources have an associated cost and study the problem of finding the cost-optimal distribution of resources throughout the nodes of the network. We analyze these questions in the context of viral spreading processes in directed networks. We study the following two problems: (i) Given a fixed budget, find the optimal allocation of preventive and corrective resources in the network to achieve the highest level of containment, and (ii) when a budget is not specified, find the minimum budget required to control the spreading process. We show that both resource allocation problems can be solved in polynomial time using Geometric Programming (GP) for arbitrary directed graphs of nonidentical nodes and a wide class of cost functions. Furthermore, our approach allows to optimize simultaneously over both preventive and corrective resources, even in the case of cost functions being node-dependent. We illustrate our approach by designing optimal protection strategies to contain an epidemic outbreak that propagates through an air transportation network.
I. INTRODUCTION
The paper formulates cost-optimal protection against spreading in weighted, directed networks using preventive and corrective resources. It addresses limitations of symmetry-based approaches with a geometric-programming formulation that applies to nonidentical agents.
- Motivation: Spreading-process control matters in epidemiology, public health, computer viruses, and cyberphysical-network security.
- Problem setting: The framework allocates preventive resources that immunize nodes and corrective resources that neutralize spreading after arrival, with costs attached to both.
- Network setting: Directed and weighted networks are emphasized because many real networks are more naturally represented with directed, weighted edges.
- Research gap: Breaking network symmetry prevents previously proposed approaches from finding optimal protection allocations for nonidentical agents.
- Contribution: Geometric programming provides a polynomial-time formulation for optimal protection allocation in weighted and directed networks.
B. Stochastic Spreading Model in Arbitrary Networks
The paper models node-dependent infection and recovery dynamics with the HeNeSIS spreading process and a mean-field approximation. Stability of the disease-free equilibrium is linked to a spectral condition on the linearized dynamics.
- Spreading model: HeNeSIS is a continuous-time networked Markov process whose nodes are susceptible or infected, with node-dependent infection and recovery rates.
- Mean-field approximation: The mean-field approximation represents each node through its marginal infection probability and reduces the process to n ordinary differential equations.
- Mean-field approximation: The mean-field dynamics use the matrix form (BAG − D)p(t) − P(t)BAGp(t), with B and D encoding infection and recovery rates.
- Stability condition: If the eigenvalue with largest real part of BAG − D satisfies the stated negative-margin condition, the disease-free equilibrium is globally exponentially stable.
- Stability condition: The linearized dynamics upper-bound the nonlinear dynamics, so stabilizing the linear approximation provides a sufficient stability condition for the mean-field model.
C. Problem Statements
The paper formulates two resource-allocation problems for containing infection spread: minimize cost for a desired decay rate or maximize decay rate under a fixed budget.
- Preventive resources reduce node infection rates, while corrective resources increase node recovery rates within feasible intervals.
- Both formulations impose bounds on infection and recovery rates and account for resource costs.
- Rate-constrained allocation: The rate-constrained problem finds the cost-optimal vaccine and antidote distribution achieving a specified exponential decay rate.
- Budget-constrained allocation: The budget-constrained problem finds the vaccine and antidote distribution maximizing exponential decay under a total budget.
- The proposed approach targets polynomial-time solutions for weighted, directed contact networks under specified cost-function assumptions.
III. A CONVEX FRAMEWORK FOR OPTIMAL RESOURCE ALLOCATION
The paper develops a geometric-programming framework for both allocation problems in weighted, directed networks, relying on convexity after logarithmic transformation and suitable cost-function structure.
- Both budget-constrained and rate-constrained allocation problems are formulated using geometric programming in weighted, directed networks.
- Geometric-programming ingredients: A monomial is a positive coefficient multiplied by decision variables raised to real powers, while a posynomial is a sum of monomials.
- Convex transformation: Functions convex in log-scale become convex after applying component-wise logarithmic variables and transforming the function arguments.
- Cost assumptions: The framework applies when the total cost is convex in log-scale, with individual costs modeled as posynomials in practical applications.
- Graph structure: The derivation uses different treatments for strongly connected and general directed graphs.
A. GP for Strongly Connected Digraphs
For strongly connected digraphs, the framework links resource allocation to spectral optimization and uses nonnegative-matrix theory to obtain geometric programs.
- The Perron-Frobenius lemma connects the spectral radius of nonnegative irreducible matrices with a positive eigenvector and a simple dominant eigenvalue.
- For positively weighted strongly connected digraphs, irreducibility enables the same spectral-radius properties for the adjacency matrix.
- The dominant eigenvalue of diag(βi)A−diag(δi) increases with infection rates and decreases with recovery rates.
- A geometric program can minimize the dominant eigenvalue of a nonnegative irreducible matrix when its entries and cost functions satisfy posynomial structure.
- These results provide solutions for both rate-constrained and budget-constrained allocation problems.
1) Solution to the Budget-Constrained Allocation Problem for Strongly Connected Digraphs:
For strongly connected graphs, the budget-constrained problem is converted into a geometric program that minimizes the spectral condition governing epidemic decay while respecting costs and rate bounds.
- The budget-constrained formulation assumes a strongly connected graph, posynomial vaccine and antidote costs, rate bounds, and a maximum protection budget.
- The optimal investment is obtained from a geometric program whose solution determines the vaccine and antidote allocations.
- Maximizing the epidemic decay rate is equivalent to minimizing the dominant eigenvalue of the controlled network matrix.
- The program includes constraints for the available budget and feasible infection and curing rates.
- A new variable and inequality preserve the optimization result while expressing the antidote-related constraint in posynomial form.
2) Solution to Rate-Constrained Allocation Problem for Strongly Connected Digraphs:
For strongly connected digraphs, the rate-constrained allocation problem is reformulated as a geometric program that computes cost-optimal infection and recovery rates under a desired exponential decay rate.
- Problem 2 is written as an optimization program for a desired exponential decay rate ε.
- Theorem 12 applies to strongly connected graphs with posynomial costs and bounded infection and recovery rates.
- The optimal vaccine and antidote investments are obtained from the GP solution for the infection and transformed recovery-rate variables.
- The spectral constraint is converted using a diagonal shift so that the relevant matrix is nonnegative and irreducible.
- The same allocation framework extends from strongly connected graphs to arbitrary directed graphs after relaxing strong connectivity.
B. Solution to Allocation Problems for General Digraphs
For general digraphs, the method handles reducible adjacency matrices by tracking zero entries in dominant eigenvectors and adapting the geometric programs accordingly.
- Perron-Frobenius positivity is unavailable for digraphs that are not strongly connected because their adjacency matrices may be reducible.
- The set Z(u) identifies the indexes of zero entries in a vector and supports the treatment of nonpositive eigenvector components.
- Adding a scalar identity shift or multiplying by a positive diagonal matrix preserves the locations of zeros in the dominant eigenvector.
- For BA − D, the dominant eigenvector has zeros in exactly the same locations as the dominant eigenvector of A.
- These zero locations allow the geometric programs to exclude decision variables associated with zero eigenvector centrality.
1) Rate-Constrained Allocation Problem for General Digraphs:
For general digraphs, the rate-constrained solution fixes rates at their minimum-investment values on zero-eigenvector-centrality nodes and solves a reduced geometric program elsewhere.
- The decision variables split into Vz for zero-eigenvector-centrality nodes and Vnz for the remaining nodes.
- For nodes in ZG, the optimal infection and recovery rates satisfy β∗_i = β_i and δ∗_i = δ_i.These rates correspond to the minimum possible investment on those nodes.
- For nodes outside ZG, the optimal rates are computed from a GP under posynomial costs, rate bounds, and a desired exponential decay rate ε.
- All decision variables in the reduced GP are strictly positive after variables associated with zero entries are handled separately.
- Theorems 17 and 19 solve the allocation problems for weighted, directed networks of nonidentical agents.
IV. NUMERICAL RESULTS
The air-transportation experiments apply the geometric programs to rate- and budget-constrained protection, revealing heterogeneous allocations of vaccines and antidotes across airports.
- ρ(AG) = 9.46, and without protection the largest eigenvalue is 0.1 > 0, so the disease-free equilibrium is unstable.The simulations therefore seek a cost-optimal allocation that stabilizes the disease-free equilibrium.
- Vaccination reduces infection rates from β̄_i to β_i, while antidotes increase recovery rates from δ_i to δ̄_i with diminishing marginal benefit.
- The rate-constrained solution assigns some airports no resources, some only corrective resources, and others a mixture of preventive and corrective resources.
- Airports with incoming traffic below 5 MPPY receive no resources, those between 5 MPPY and 8 MPPY receive only corrective resources, and those above 8 MPPY receive both types.
- A budget 50% above the optimal budget for ε = 10^-3 achieves an exponential decay rate of ε∗ = 0.342.
- Under the extra budget, every airport receives protection and all receive corrective resources, while some receive no preventive resources.
V. CONCLUSIONS
The paper develops polynomial-time protection-resource allocation for weighted, directed networks with nonidentical agents, covering preventive and corrective resources. It demonstrates the approach on a real air transportation network, where optimal allocations for a hypothetical pandemic exhibit nontrivial patterns beyond simple centrality heuristics.
- The study addresses preventive resources that immunize nodes and corrective resources that neutralize spreading after it reaches a node.Examples include vaccines and antidotes.
- The framework solves optimal resource allocation in weighted, directed networks of nonidentical agents in polynomial time using Geometric Programming.It supports simultaneous optimization over preventive and corrective resources with node-dependent cost functions.
- The approach designs an optimal protection strategy for a real air transportation network.The application concerns containing a hypothetical worldwide pandemic.
- Optimal resource distributions in the busiest-airport network follow nontrivial patterns that simple heuristics based on traditional centrality measures cannot generally describe.The study is limited to the network of the world’s busiest airports by passenger traffic.
APPENDIX
The appendix develops spectral arguments for directed-network spreading models, including perturbation effects and transformations that preserve dominant-eigenvector zero locations. It also introduces the binary stochastic node-state representation of the HeNeSIS model.
- Spectral properties: A shifted auxiliary matrix makes the relevant matrix nonnegative and irreducible for strongly connected graphs, enabling positive left and right dominant eigenvectors.The construction uses M = diag(β_i)A − diag(δ_i) + ∆I with ∆ = max{δ_i}.
- Perturbation analysis: Eigenvalue perturbation theory expresses the first-order spectral-radius change as w^T∆Mv + o(∥∆M∥).Here v and w are the right and left dominant eigenvectors of M.
- Perturbation analysis: A positive increment in β_k increases the spectral radius because the perturbation term is positive.The perturbation is defined as ∆B = ∆β_k e_k e_k^T A.
- Spectral properties: The appendix proves that corresponding left and right dominant eigenvectors have identical zero locations.This establishes Z(u) = Z(w) through component-wise nonnegativity arguments.
- Matrix transformations: Transformations applied to BA − D preserve the locations of zeros in the dominant eigenvector through the final matrix A.The chain shifts, rescales, and transforms the matrix while preserving Z(v_1(BA − D)) = Z(v_1(A)).