Blocking links to minimize contamination spread in a social network
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 01, 2009
- Source ID
- 10.1145/1514888.1514892
Entities
People
- Hiroshi Motoda
- Kazumi SaitÅ
- Masahiro Kimura
Organizations
- Air Force Research Laboratory
- Japan Society for the Promotion of Science
- Osaka University
- Ryukoku University
- University of Shizuoka