In this paper we address the problem of identifying the most likely infection pattern responsible for the spread of a disease in a network. In particular, we focus on the scenario where limited information (i.e. infection reports) is available during an ongoing outbreak. For this problem we propose a maximum likelihood model and present an integer programming formulation. The objective of the model is to identify the most likely directed tree that spans to a set of known infected nodes, subject to path feasibility constraints. We propose a new solution method based on a three step heuristic which (1) reduces the initial graph using a polynomial time algorithm designed to find a subset of feasible infection paths, (2) ranks these paths using lower and upper bounds on their likelihood and generates multiple subgraphs containing a variable level of information, and (3) solves an exact mixed integer linear programming reformulation of the maximum likelihood model. Simulated contagion episodes are used to evaluate the performance of our solution method. Our results show that the approach is computationaly efficient and is able to reconstruct a significant proportion of the outbreak, even in the context of low levels of information availability.
Citation
School of Civil and Environmental Engineering, University of New South Wales, Sydney, 2052, NSW, Australia. November, 2013.
Article
View Finding the Most Likely Infection Path in Networks with Limited Information