title: Inferring the origin of an epidemic with a dynamic message-passing algorithm.
abstract: We study the problem of estimating the origin of an epidemic outbreak: given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. This problem is important in different contexts of computer or social networks. Assuming that the epidemic spread follows the usual susceptible-infected-recovered model, we introduce an inference algorithm based on dynamic message-passing equations and we show that it leads to significant improvement of performance compared to existing approaches. Importantly, this algorithm remains efficient in the case where the snapshot sees only a part of the network.
authors.affiliation: LPTMS, Université Paris-Sud and CNRS-UMR 8626, 91405 Orsay, France.
authors.forename: Andrey Y
authors.initials: AY
authors.lastname: Lokhov
authors.affiliation: LPTMS, Université Paris-Sud and CNRS-UMR 8626, 91405 Orsay, France and Ecole Normale Supérieure, 45 rue d'Ulm, 75005 Paris, France.
authors.forename: Marc
authors.initials: M
authors.lastname: Mézard
authors.affiliation: LPTMS, Université Paris-Sud and CNRS-UMR 8626, 91405 Orsay, France.
authors.forename: Hiroki
authors.initials: H
authors.lastname: Ohta
authors.affiliation: IPhT, CEA Saclay and CNRS-URA 2306, 91191 Gif-sur-Yvette, France.
authors.forename: Lenka
authors.initials: L
authors.lastname: Zdeborová
mesh_terms: D000465:Algorithms; D004198:Disease Susceptibility; D058872:Epidemics; D007239:Infections / Q000453:epidemiology / Q000635:transmission; D008962:Models, Theoretical