Node-securing connectivity-based model to reduce infection spread in contaminated networks

摘要

Given a network with a set of contaminated and susceptible nodes, this article presents models for identifying a subset of susceptible nodes to secure (e.g., guard against infection, or remove from the network) such that the total number of nodes at risk of infection is minimized, subject to a limited budget for securing nodes. These models utilize a connectivity-based metric, in which a susceptible node is assumed to be at risk of infection if there exists a transmission path between it and any infected node, where no transmission path exists between two nodes if every path between them includes at least one secured node. The initial model presented, which is to the authors' knowledge the first node-securing connectivity-based model for mitigating the spread of infection in contaminated networks, is then reformulated by use of a novel search space reduction algorithm. Computational testing is presented demonstrating the significant reductions in solution time achieved by the reformulated model.