Timezone: »

Diffusion Source Identification on Networks with Statistical Confidence
Quinlan Dawkins · Tianxi Li · Haifeng Xu

Wed Jul 21 09:00 PM -- 11:00 PM (PDT) @

Diffusion source identification on networks is a problem of fundamental importance in a broad class of applications, including controlling the spreading of rumors on social media, identifying a computer virus over cyber networks, or identifying the disease center during epidemiology. Though this problem has received significant recent attention, most known approaches are well-studied in only very restrictive settings and lack theoretical guarantees for more realistic networks. We introduce a statistical framework for the study of this problem and develop a confidence set inference approach inspired by hypothesis testing. Our method efficiently produces a small subset of nodes, which provably covers the source node with any pre-specified confidence level without restrictive assumptions on network structures. To our knowledge, this is the first diffusion source identification method with a practically useful theoretical guarantee on general networks. We demonstrate our approach via extensive synthetic experiments on well-known random network models, a large data set of real-world networks as well as a mobility network between cities concerning the COVID-19 spreading in January 2020.

Author Information

Quinlan Dawkins (University of Virginia)
Tianxi Li (University of Virginia)
Haifeng Xu (University of Virginia)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors