Efficient Edge Immunization Strategies for Diffusion Containment in Social Networks

We study algorithmic strategies to effectively contain diffusion via edge immunization. We consider the scenarios where the epidemic characteristics are known and unknown, and accordingly present approaches relying upon the epidemic dynamics and the network topology. In particular, for the former, we propose the greedy and inverse greedy immune schemes to greedily minimize the immune edge set, whose performance is guaranteed by the exhaustive search. We also present strategies to scale up the associated methods such that they can more efficiently obtain better solutions. For the latter, we find that the epidemic incidence of the immunized network is determined by both local and global connection patterns, characterized by the critical threshold in network epidemiology and the largest connected component in network percolation, respectively. Thus, we propose network topology-based strategies that obtain the immune edge set by simultaneously minimizing both the factors. We conduct extensive experiments on synthetic and empirical social networks to evaluate the proposed methods. Results show that our methods outperform the state-of-the-art by a large margin. Besides, the developed topology-based strategies can always obtain comparable results to the greedy strategies, which are computationally much cheaper than existing approaches and thus favorable to tackle large-scale networks.