Network node immunization: improving Netshield algorithm through random rooted forests
This work addresses the problem of efficiently selecting nodes to remove in order to minimize virus spread in networks, which is important for network security and epidemiology.
The authors propose a new algorithm, K-shield, for the multiple-node immunization problem in complex networks, which improves upon the existing Netshield algorithm by achieving better searching performance at the same computational complexity. Numerical experiments on various benchmarks demonstrate the effectiveness of K-shield.
We are interested in the so-called multiple-node immunization problem for complex networks under attack by a viral agent. It consists in identifying and removing a set of nodes of size $k$ in a graph to maximize the impeding of virus spread. A few approaches have been proposed in the literature based on numerical and theoretical insights on how classical models for virus spread evolve on graphs. Based on the analysis of these models, the maximal eigenvalue of the adjacency matrix of the graph has become a classical measure of how resilient the network is. Thus, a clear, well-explored approach for multiple-node immunization consists of identifying a set of $k$ nodes in such a way that the reduced network, obtained by removing these nodes, has a minimal largest eigenvalue. This spectral optimization problem turns out to be a computationally hard problem for which only greedy algorithms offer good solutions at efficient computational time. Among those, the so-called Netshield algorithm represents one of the reference choices. The latter is, in fact, a clearly defined algorithm aiming at optimizing a certain sub-modular functional, called shield-value, which approximates the original optimization problem. We propose here a novel procedure, based on random walk kernels and related random spanning forests, to build a new algorithm, referred to as K-shield, which enhances Netshield searching performance at the same computational complexity. We give theoretical insights behind this novel method, which could also be used for other optimization problems, and then test it via numerical showcase experiments on various benchmarks.