Effective and scalable methods for graph protection strategies against epidemics on dynamic networks

Abstract

Abstract Dynamic networks are networks with temporal relationship features which evolve over time by the inclusion and deletion of nodes and edges. Suppressing the epidemic spreading in such networks is quite challenging. The problem of protecting a limited number of nodes to restrain the spreading of malicious attacks or dangerous rumor in the networks is called graph protection problem. However, most of existing strategies only consider to protect at once regardless the evolving network structure and incoming attacks over time, i.e., these strategies either pre-protect important nodes before the epidemic starts or post-allocate the protection while the attacks have already spread over the network. In this paper, we introduce multiple-turns protection strategies, which divide the size of protection budget into several turns and protect nodes according to the currently observed temporal snapshot of dynamic networks. We construct a minimum vertex cover of the input network efficiently using reinforcement learning approach. To capture the state of the input network, a feature-based representation of each node is constructed using a graph embedding technique. Experimental evaluations show that our proposed methods, namely ReProtect and ReProtect-p effectively restrain epidemic propagation in synthetic and real-world network datasets. By protecting about 15% of nodes, our methods can obtain up to 84% of surviving nodes and outperform other baseline methods on two popular epidemic models: SIS and SIR.

Keywords

• Graph protection
• Node immunization
• Dynamic networks
• Reinforcement learning