Multiple Node Immunisation for Preventing Epidemics on Networks by Exact Multiobjective Optimisation of Cost and Shield-Value
The general problem in this paper is vertex (node) subset selection with the goal to contain an infection that spreads in a network. Instead of selecting the single most important node, this paper deals with the problem of selecting multiple nodes for removal. As compared to previous work on multiple-node selection, the trade-off between cost and benefit is considered. The benefit is measured in terms of increasing the epidemic threshold which is a measure of how difficult it is for an infection to spread in a network. The cost is measured in terms of the number and size of nodes to be removed or controlled. Already in its single-objective instance with a fixed number of $k$ nodes to be removed, the multiple vertex immunisation problems have been proven to be NP-hard. Several heuristics have been developed to approximate the problem. In this work, we compare meta-heuristic techniques with exact methods on the Shield-value, which is a sub-modular proxy for the maximal eigenvalue and used in the current state-of-the-art greedy node-removal strategies. We generalise it to the multi-objective case and replace the greedy algorithm by a quadratic program (QP), which then can be solved with exact QP solvers. The main contribution of this paper is the insight that, if time permits, exact and problem-specific methods approximation should be used, which are often far better than Pareto front approximations obtained by general meta-heuristics. Based on these, it will be more effective to develop strategies for controlling real-world networks when the goal is to prevent or contain epidemic outbreaks. This paper is supported by ready to use Python implementation of the optimization methods and datasets.
Code (1)
Similar Papers 제목 키워드 기반
Compact pairwise models for epidemics with multiple infectious stages on degree heterogeneous and clustered networks
This paper presents a compact pairwise model that describes the spread of multi-stage epidemics on networks. The multi-stage model corresponds to a gamma-distributed infectious period which interpolates between the class…
ClusteringIdentifying Asymptomatic Nodes in Network Epidemics using Graph Neural Networks
Infected individuals in some epidemics can remain asymptomatic while still carrying and transmitting the infection. These individuals contribute to the spread of the epidemic and pose a significant challenge to public he…
Graph Neural NetworkBackward and Forward Inference in Interacting Independent-Cascade Processes: A Scalable and Convergent Message-Passing Approach
We study the problems of estimating the past and future evolutions of two diffusion processes that spread concurrently on a network. Specifically, given a known network $G=(V, \overrightarrow{E})$ and a (possibly noisy) …
Spread Control Method on Unknown Networks Based on Hierarchical Reinforcement Learning
Epidemics such as COVID-19 pose serious threats to public health and our society, and it is critical to investigate effective methods to control the spread of epidemics over networks. Prior works on epidemic control ofte…
Hierarchical Reinforcement Learningreinforcement-learningvalidLearning Graphs from Noisy Epidemic Cascades
We consider the problem of learning the weighted edges of a graph by observing the noisy times of infection for multiple epidemic cascades on this graph. Past work has considered this problem when the cascade information…