Diffusion Source Identification on Networks with Statistical Confidence

Identifying the source of spread through a network, termed diffusion source identification, is a problem of fundamental importance in a broad class of applications such as rumor controlling and virus identification. Though this problem has received significant recent attention, most studies have focused only on very restrictive settings and lack theoretical guarantees for real-world network topologies. This work introduces a statistical framework for diffusion source identification for a broad class of diffusion processes on general network topologies. It also develops a confidence set inference approach inspired by statistical hypothesis testing. Our method efficiently produces a small subset of nodes, which provably covers the source node with any pre-specified confidence level. Multiple Monte Carlo strategies are presented for the inference procedure based on network topology and the probabilistic properties that significantly improve the scalability. To our knowledge, this is the first diffusion source identification method with a practically useful theoretical guarantee on general networks. The proposed method is evaluated by extensive synthetic experiments based on well-known random network models and real-world networks from several domains. The method is also demonstrated in a real-world diffusion example concerning the spread of COVID-19 between cities.