Blocking links to minimize contamination spread in a social network

TLDR

Minimizing the spread of undesirable content by blocking links in a network is a fundamental problem, distinct from influence maximization and more basic than node removal strategies. The study introduces two contamination‑degree definitions, formulates two minimization problems, and proposes greedy‑based approximation methods. The authors use a greedy strategy to efficiently approximate solutions to the two defined contamination‑minimization problems. Experiments on large social networks show that the greedy methods outperform conventional link‑removal techniques, and that high‑out‑degree node removal is not always effective.

Abstract

We address the problem of minimizing the propagation of undesirable things, such as computer viruses or malicious rumors, by blocking a limited number of links in a network, which is converse to the influence maximization problem in which the most influential nodes for information diffusion is searched in a social network. This minimization problem is more fundamental than the problem of preventing the spread of contamination by removing nodes in a network. We introduce two definitions for the contamination degree of a network, accordingly define two contamination minimization problems, and propose methods for efficiently finding good approximate solutions to these problems on the basis of a naturally greedy strategy. Using large social networks, we experimentally demonstrate that the proposed methods outperform conventional link-removal methods. We also show that unlike the case of blocking a limited number of nodes, the strategy of removing nodes with high out-degrees is not necessarily effective for these problems.