Finding Outbreak Trees in Networks with Limited Information

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • David Rey - , University of New South Wales (Autor:in)
  • Lauren Gardner - , University of New South Wales (Autor:in)
  • S. Travis Waller - , University of New South Wales (Autor:in)

Abstract

Real-time control of infectious disease outbreaks represents one of the greatest epidemiological challenges currently faced. In this paper we address the problem of identifying contagion patterns responsible for the spread of a disease in a network, which can be applied in real-time to evaluate an ongoing outbreak. We focus on the scenario where limited information, i.e. infection reports which may or may not include the actual source, is available during an ongoing outbreak and we seek the most likely infection tree that spans at least a set of known infected nodes. This problem can be represented using a maximum likelihood constrained Steiner tree model where the objective is to find a spanning tree with an assignment of integer nodes weights. We propose a novel formulation and solution method based on a two-step heuristic which (1) reduces the initial graph using a polynomial time algorithm designed to find feasible infection paths and (2) solves an exact mixed integer linear programming reformulation of the maximum likelihood model on the resulting subgraph. The proposed methodology can be applied to outbreaks which may evolve from multiple sources. Simulated contagion episodes are used to evaluate the performance of our solution method. Our results show that the approach is computationally efficient and is able to reconstruct a significant proportion of the outbreak, even in the context of low levels of information availability.

Details

OriginalspracheEnglisch
Seiten (von - bis)687-721
Seitenumfang35
FachzeitschriftNetworks and Spatial Economics
Jahrgang16
Ausgabenummer2
PublikationsstatusVeröffentlicht - 1 Juni 2016
Peer-Review-StatusJa
Extern publiziertJa

Externe IDs

ORCID /0000-0002-2939-2090/work/141543806

Schlagworte

Ziele für nachhaltige Entwicklung

Schlagwörter

  • Contagion patterns, Integer programming, Network optimization, Shortest path, Social contact networks