Masahiro Kimura, Kazumi Saito, Hiroshi Motoda
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, a dual problem to the influence maximization problem of finding the most influential nodes in a social network for information diffusion. This minimization problem is another approach to the problem of preventing the spread of contamination by removing nodes in a network. We propose a method for efficiently finding a good approximate solution to this problem based on a naturally greedy strategy. Using large real networks, we demonstrate experimentally that the proposed method significantly outperforms conventional link-removal methods. We also show that unlike the strategy of removing nodes, blocking links between nodes with high out-degrees is not necessarily effective.
Subjects: 12. Machine Learning and Discovery; 3.4 Probabilistic Reasoning
Submitted: Apr 8, 2008