Algorithms for massive multi-hop contact tracing

Contact tracing has been proposed as one of the techniques that try to solve the problem of containing the spread of a pandemic by identifying at-risk individuals tracing their contacts and promptly suggesting them to test for positivity. However, during the recent breakout of Covid-19 this methodology has proven itself to be inconclusive, due to the vast majority of individuals being asymptomatic. Most of the time individuals have no way of knowing whether they are infectious if they do not show symptoms related to the disease, thus increasing the chance of them spreading the infection to their contacts. In this work, first, we study a the framework that models social interactions between individuals using temporal graphs and finally develop an algorithm that computes the infectious paths on a given temporal graph, finding the h-hop risky contacts of the individuals. Using this information we can ultimately classify each node as sick or not sick depending on the amount of risky direct and indirect contacts they had in the last 15 days. Lastly we show how our methodology based on multihop contact tracing is able to outperform other classification approaches by testing our algorithm on synthetic and natural temporal graphs of various sizes. In addition, we provide an approximation algorithm to be able to compute the h-hop risky contacts also on accurate temporal graphs, by exploiting sets approximation and proving the capability of the approximated version to outperform our exact version by maintaining the same classification accuracy.