Abstract:
|
We consider a problem of optimally allocating resources for suppressing epidemic spreads in a directed weighted network, where the spreading dynamic exhibits a phase transition depending on the contact network structure and the heterogeneous infection and curing rates. This phase transition is captured by a critical threshold: below which the spread dies out quickly; otherwise an outbreak occurs. We show that solutions to this problem can be derived from that of a matrix balancing problem, for which efficient centralized algorithms exist. For large scale networks, we propose an improved variant of a classical matrix balancing algorithm that admits a better convergence rate and is more amenable for parallel and even asynchronous distributed implementations. Moreover, we show that for a large class of graphs, including random graphs, our algorithm runs in nearly linear time.
|