Journal of Biomedical Informatics

Dynamic graph and polynomial chaos based models for contact tracing data analysis and optimal testing prescription

Download paper


In this study, we address three important challenges related to disease transmissions such as the COVID-19 pandemic, namely, (a) providing an early warning to likely exposed individuals, (b) identifying individuals who are asymptomatic, and (c) prescription of optimal testing when testing capacity is limited. First, we present a dynamic-graph based SEIR epidemiological model in order to describe the dynamics of the disease propagation. Our model considers a dynamic graph/network that accounts for the interactions between individuals over time, such as the ones obtained by manual or automated contact tracing, and uses a diffusion–reaction mechanism to describe the state dynamics. This dynamic graph model helps identify likely exposed/infected individuals to whom we can provide early warnings, even before they display any symptoms and/or are asymptomatic. Moreover, when the testing capacity is limited compared to the population size, reliable estimation of individual's health state and disease transmissibility using epidemiological models is extremely challenging. Thus, estimation of state uncertainty is paramount for both eminent risk assessment, as well as for closing the tracing-testing loop by optimal testing prescription. Therefore, we propose the use of arbitrary Polynomial Chaos Expansion, a popular technique used for uncertainty quantification, to represent the states, and quantify the uncertainties in the dynamic model. This design enables us to assign uncertainty of the state of each individual, and consequently optimize the testing as to reduce the overall uncertainty given a constrained testing budget. These tools can also be used to optimize vaccine distribution to curb the disease spread when limited vaccines are available. We present a few simulation results that illustrate the performance of the proposed framework, and estimate the impact of incomplete contact tracing data.


01 Oct 2021


Journal of Biomedical Informatics