Fast Outbreak Sense and Effective Source Inference via Minimum Observer Set

This paper addresses the Fast outbreak Sensing and Effective diffusion source Inferring (FSEI) problem, which assumes that the state of nodes in a particularly chosen observer set can be monitored if necessary and aims to optimize the observer set such that outbreaks can be timely detected and their sources can be effectively targeted. We propose three approaches to tackle the FSEI problem: Greedy Strategy (GS), Network-Topology-based Method (NTM), and Hybrid Method (HM). Among them, GS relies on collected outbreaks and constructs the observer set by iteratively choosing and removing the node that minimizes the product of sensing time and source targeting cost of the remaining network. For NTM, we also consider the remaining network and introduce a novel strategy to optimize its topology via simultaneously minimizing the adjoining component size and ratio of the first and second moments. HM is a combination of GS and NTM, considering the submodular property of GS on the minimization of the sensing time and well approximation of the component size on the optimization of the source targeting. We perform extensive experiments on over 200 empirical networks, using various diffusion models, to validate the proposed methods. The results demonstrate that our approaches consistently outperform the state-of-the-art. We believe that the model and methodology presented in this paper can be readily applied to real-world scenarios such as combating misinformation and controlling diffusions of information or disease.