Methods for removing links in a network to minimize the spread of infections

摘要

Minimizing the spread of infections is a challenging problem, and it is the subject matter in many different fields such as epidemiology and cyber-security. In this paper, we investigate link removal as an intervention strategy and study the relative effectiveness of different link removal methods in minimizing the spread of infections in a network. With that in mind, we develop four connectivity-based network interdiction models and formulate these models as mixed integer linear programs. The first model minimizes the number of connections between infected and susceptible nodes; the second the number of susceptible nodes having one or more connections with infected nodes; the third the total number of paths between infected and susceptible nodes; and the fourth the total weight of the paths between infected and susceptible nodes. We also propose heuristic algorithms to solve the models. The network interdiction models act as link removal methods, i.e., each return a solution consisting of a set of links to remove in the network. We compare the effectiveness of these four methods with the effectiveness of an existing link removal method [25], a method based on link betweenness centrality [18], and random link removal method. Our results show that complete isolation of susceptible nodes from infected nodes is the most effective method in reducing the average number of new infections (reduce occurrence) under most scenarios, and the relative effectiveness of the complete isolation method increases with transmission probability. In contrast, removing the highest probability transmission paths is the most effective method in increasing the average time to infect half of the susceptible nodes (reduce speed) under most scenarios, and the relative effectiveness of this method decreases with transmission probability. (C) 2015 Elsevier Ltd. All rights reserved.