Models and algorithms for network immunization

Recently, there has been significant research activity in the algorithmic analysis of complex networks, such as so-cial networks, or information networks. A problem of great practical importance is that of network immunization against virus spread. Given a network, a virus-propagation model, and an immunization cost function, we are interested in containing the spread of the virus while minimizing the immunization cost. In this paper, we consider two virus-propagation models and we propose immunization algo-rithms for each model. The experimental evaluation shows that our algorithms perform well on both synthetic and real graphs. Furthermore, it reveals the following interesting facts (a) the simple heuristic of immunizing the nodes with the highest degree is not optimal, and (b) our algorithms perform significantly better in small-world networks.