Optimal Resource Allocation for Network Protection Against Spreading Processes
Optimal Resource Allocation for Network Protection Against Spreading Processes
复制标题
DOI：
10.1109/tcns.2014.2310911
复制
发表时间：
2014-03-01
影响因子：
4.2
通讯作者：
Pappas, George J.
中科院分区：
文献类型：
--
作者：
Preciado, Victor M.;Zargham, Michael;Pappas, George J.
我们研究了在任意有向网络中通过在网络的各个节点上分配保护资源来抑制扩散过程的问题。我们认为有两种类型的保护资源可用：1）预防性资源能够保护节点免受传播（如病毒感染过程中的疫苗），2）纠正性资源能够在传播到达节点后中和传播（如解毒剂）。我们假设预防性和纠正性资源都有相关的成本，并研究在网络的各个节点上找到资源的成本最优分布的问题。我们分析这些问题的背景下，在有向网络中的病毒传播过程。我们研究了以下两个问题：1）给定一个固定的预算，在网络中找到预防和纠正资源的最佳分配，以实现最高水平的遏制和2）当预算是不指定的，找到所需的最小预算控制的蔓延过程。我们表明，这两个资源分配问题可以解决在多项式时间内使用几何规划（GP）的任意有向图的不相同的节点和广泛的一类成本函数。我们通过设计最佳保护策略来说明我们的方法，以遏制通过航空运输网络传播的流行病爆发。
We study the problem of containing spreading processes in arbitrary directed networks by distributing protection resources throughout the nodes of the network. We consider that two types of protection resources are available: 1) preventive resources able to defend nodes against the spreading (such as vaccines in a viral infection process) and 2) 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: 1) given a fixed budget, find the optimal allocation of preventive and corrective resources in the network to achieve the highest level of containment and 2) when a budget is not specified, find the minimum budget required to control the spreading process. We show that both the 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. We illustrate our approach by designing optimal protection strategies to contain an epidemic outbreak that propagates through an air transportation network.