On Temporal Bipartite Graphs and Their Application in Disease Spread Prediction

Abstract

The original temporal bipartite graph is flawed in the context of disease spreading models as it does not account for concepts such as virus incu-bation and recovery periods. In this thesis, a new graph structure, referred to as the improved temporal bipartite graph is introduced with these two concepts incorporated to enhance accuracy in predicting disease spreading. To facilitate arbitrary reachability queries, another concept, the transmission graph, is introduced. It is derived from a temporal bipartite graph based on a series of reachability query evaluation. We distinguish between two types: single-path transmission graph and multi-path trans-mission graph. Based on them, four algorithms are proposed for evaluating reachability queries on a temporal bipartite graph, with a label-based technique used to achieve high efficiency. Both single-path transmission graphs and multi-path transmission graphs are in fact a kind of extension of the reachability query evaluation. By establishing indexes over them, the reachability query evaluation for disease spreading prediction can be very efficiently conducted.