Options
On reconstructing the patient zero from sensor measurements
Publikationstyp
Conference Paper
Date Issued
2023-07
Sprache
English
Author(s)
Kaaser, Dominik
Volume
2023-July
Start Page
671
End Page
681
Citation
43rd IEEE International Conference on Distributed Computing Systems (ICDCS 2023)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Institute of Electrical and Electronics Engineers Inc.
ISBN
9798350339864
Epidemic spreading processes have been widely studied over the last years, with an additional boost due to the ongoing COVID-19 pandemic. However, epidemic spreading is not limited to infectious diseases; it forms the basis of understanding opinion formation processes in social networks, or models the spread of computer viruses in network security. In all of these application domains, the forward processes are typically well understood, both from a theoretical and a practical point of view. Interestingly, much less is known about the converse direction: suppose we are given 'sensors' that report on the infection status, can we recover the source of the epidemic' This problem is known under the name of patient zero, rumor source detection, or finding the point of entrance in the context of intrusion detection systems. In this work we assume that the epidemic process spreads according to the classical Independent Cascade Model, and we are given sensors on edges of the communication network. We rigorously analyze under which sensor placement one can recover the source of the epidemic process. Our main contribution is an impossibility result: we formally prove a lower bound on the number of sensors required to recover the source of the epidemic process. Furthermore, we introduce a monitoring strategy that succeeds in recovering the patient zero with the minimum number of sensors possible for acyclic networks. Finally, we discuss unreliable sensor measurements and provide extensive simulations of according heuristics on realistic communication networks.
Subjects
Epidemic Spreading
Independent Cascade Model
Inference
Patient Zero
Rumor Source Detection
SIR
DDC Class
620: Engineering