Various complex systems are exposed to different kinds of infections ranging from computer viruses to rumors. An intuitive solution for limiting the damages caused by such infections is to detect the infection spreading as early as possible and then take necessary actions. In this paper, we study on how much we may expect to achieve in infection control by deploying a number of monitors in complex networks for detecting the outbreak of a strong infection at its early stage. Specifically, we consider the problem of finding the optimal locations for a given number of monitors in order to minimize the worst-case infection size. The NP-hardness of the problem is proved and a heuristic algorithm is proposed. Extensive simulations on both synthetic and real-life networks show that the worst-case infection size may be put under control by deploying a moderate number of monitors in a large complex network. Effects of a few different factors, including transmissibility of the infection, network topology and probability of detection failure, are also evaluated.
展开▼
