Optimization Online


Finding the Most Likely Infection Path in Networks with Limited Information

David Rey(d.rey***at***unsw.edu.au)
Lauren Gardner(l.gardner***at***unsw.edu.au)
S. Travis Waller(s.waller***at***unsw.edu.au)

Abstract: 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.

Keywords: Network Optimization, Integer Programming, Contagion Processes, Length Constrained Shortest Path, k Shortest Paths

Category 1: Network Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- Science and Engineering (Biomedical Applications )

Citation: School of Civil and Environmental Engineering, University of New South Wales, Sydney, 2052, NSW, Australia. November, 2013.

Download: [PDF]

Entry Submitted: 12/11/2013
Entry Accepted: 12/17/2013
Entry Last Modified: 12/11/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society