The patient-zero problem with noisy observations. (English) Zbl 1456.92129
Summary: A belief propagation approach has been recently proposed for the patient-zero problem in SIR epidemics. The patient-zero problem consists of finding the initial source of an epidemic outbreak given observations at a later time. In this work, we study a more difficult but related inference problem, in which observations are noisy and there is confusion between observed states. In addition to studying the patient-zero problem, we also tackle the problem of completing and correcting the observations to possibly find undiscovered infected individuals and false test results.
Moreover, we devise a set of equations, based on the variational expression of the Bethe free energy, to find the patient-zero along with maximum-likelihood epidemic parameters. We show, by means of simulated epidemics, that this method is able to infer details on the past history of an epidemic outbreak based solely on the topology of the contact network and a single snapshot of partial and noisy observations.
MSC:
| 92D30 | Epidemiology |
References:
| [1] | Bailey N T J 1975 The Mathematical Theory of Infectious Diseases and Its Applications (London: Griffin) · Zbl 0334.92024 |
| [2] | Kermack W O and McKendrick A G 1927 Proc. R. Soc. Lond. A 115 700 · JFM 53.0517.01 · doi:10.1098/rspa.1927.0118 |
| [3] | Isella L, Stehlé J, Barrat A, Cattuto C, Pinton J-F and Van den Broeck W 2011 J. Theor. Biol.271 166 · Zbl 1405.92255 · doi:10.1016/j.jtbi.2010.11.033 |
| [4] | Rocha L E C, Liljeros F and Holme P 2010 Proc. Natl Acad. Sci.107 5706 · Zbl 1205.91145 · doi:10.1073/pnas.0914080107 |
| [5] | Danon L, Ford A P, House T, Jewell C P, Keeling M J, Roberts G O, Ross J V and Vernon M C 2011 Interdiscip. Perspect. Infect. Dis.2011 284909 · doi:10.1155/2011/284909 |
| [6] | Marathe M and Vullikanti A K S 2013 Commun. ACM56 88-96 · doi:10.1145/2483852.2483871 |
| [7] | Shah D and Zaman T 2010 ACM Sigmetrics Perform. Eval. Rev.38 203 · doi:10.1145/1811099.1811063 |
| [8] | Comin C H and da Fontoura Costa L 2011 Phys. Rev. E 84 056105 · doi:10.1103/PhysRevE.84.056105 |
| [9] | Shah D and Zaman T 2011 IEEE Trans. Inform. Theory57 5163-81 · Zbl 1366.91126 · doi:10.1109/TIT.2011.2158885 |
| [10] | Fioriti V and Chinnici M 2012 arXiv:1211.2333 |
| [11] | Pinto P C, Thiran P and Vetterli M 2012 Phys. Rev. Lett.109 068702 · doi:10.1103/PhysRevLett.109.068702 |
| [12] | Antulov-Fantulin N, Lancic A, Stefancic H, Sikic M and Smuc T 2013 Statistical inference framework for source detection of contagion processes on arbitrary network structures |
| [13] | Dong W, Zhang W and Tan C W 2013 IEEE Int. Symp. on Information Theory Proc.(Istanbul, 7-12 July 2013) pp 2671-5 |
| [14] | Lokhov A Y, Mézard M, Ohta H and Zdeborová L 2014 Phys. Rev. E 90 012801 · doi:10.1103/PhysRevE.90.012801 |
| [15] | Luo W, Tay W P and Leng M 2013 IEEE Trans. Signal Process.61 2850 · Zbl 1393.94594 · doi:10.1109/TSP.2013.2256902 |
| [16] | Zhu K and Ying L 2013 Information Theory and Applications Workshop(San Diego, CA, 10-15 Febraury 2013) pp 1-9 |
| [17] | Karamchandani N and Franceschetti M 2013 IEEE Int. Symp. on Information Theory Proc.(Istanbul, 7-12 July 2013) pp 2184-8 |
| [18] | Altarelli F, Braunstein A, Dall’Asta L, Lage-Castellanos A and Zecchina R 2014 Phys. Rev. Lett.112 118701 · doi:10.1103/PhysRevLett.112.118701 |
| [19] | Karrer B and Newman M E J 2010 Phys. Rev. E 82 016101 · doi:10.1103/PhysRevE.82.016101 |
| [20] | Milling C, Caramanis C, Mannor S and Shakkottai S 2013 Proc. 14th ACM Int. Symp. on Mobile ad Hoc Networking and Computing(Bangalore, India, 29 July-1 August 2013) pp 177-86 |
| [21] | Meirom E A, Milling C, Caramanis C, Mannor S, Orda A and Shakkottai S 2014 arXiv:1402.1263 |
| [22] | Kermack W O and McKendrick A G 1932 Proc. R. Soc. A 138 55 · Zbl 0005.30501 · doi:10.1098/rspa.1932.0171 |
| [23] | Bayati M, Shah D and Sharma M 2008 IEEE Trans. Inform. Theory54 1241 · Zbl 1311.90161 · doi:10.1109/TIT.2007.915695 |
| [24] | Bayati M, Braunstein A and Zecchina R 2008 J. Math. Phys.49 125206 · Zbl 1159.81303 · doi:10.1063/1.2982805 |
| [25] | Gamarnik D, Shah D and Wei Y 2010 Belief Propagation for Min-Cost Network Flow: Convergence and Correctness (Society for Industrial and Applied Mathematics) National Science Foundation (US) (Project CMMI-0726733) |
| [26] | Weiss Y and Freeman W T 2001 Neural Comput.13 2173 · Zbl 0992.68055 · doi:10.1162/089976601750541769 |
| [27] | Bayati M and Nair C 2006 A rigorous proof of the cavity method for counting matchings Allerton Conf. on Communication, Control and Computing(Allerton,) |
| [28] | Altarelli F, Braunstein A, Dall’Asta L and Zecchina R 2013 Phys. Rev. E 87 062115 · doi:10.1103/PhysRevE.87.062115 |
| [29] | Altarelli F, Braunstein A, Dall’Asta L and Zecchina R 2013 J. Stat. Mech. P09011 · Zbl 1456.82420 |
| [30] | Yedidia J S, Freeman W T and Weiss Y 2000 NIPS13 689-95 |
| [31] | Mézard M and Montanari A 2009 Information, Physics and Computation (New York: Oxford University Press) · Zbl 1163.94001 · doi:10.1093/acprof:oso/9780198570837.001.0001 |
| [32] | Barabási A-L and Albert R 1999 Science286 509 · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
