Kemeny-based testing for COVID-19

Abstract

Testing, tracking and tracing abilities have been identified as pivotal in helping countries to safely reopen activities after the first wave of the COVID-19 virus. Contact tracing apps give the unprecedented possibility to reconstruct graphs of daily contacts, so the question is who should be tested? As human contact networks are known to exhibit community structure, in this paper we show that the Kemeny constant of a graph can be used to identify and analyze bridges between communities in a graph. Our "Kemeny indicator" is the change in Kemeny constant when a node or edge is removed from the graph. We show that testing individuals who are associated with large values of the Kemeny indicator can help in efficiently intercepting new virus outbreaks, when they are still in their early stage. Extensive simulations provide promising results in early identification and in blocking possible "super-spreaders" links that transmit disease between different communities.

References in corpus (6)

• A SIDARTHE Model of COVID-19 Epidemic in Italy
• Efficient Immunization Strategies for Computer Networks and Populations
• Individualization as driving force of clustering phenomena in humans
• A Note on the PageRank of Undirected Graphs
• The Kemeny constant of a Markov chain
• Spatial Positioning Token (SPToken) for Smart Mobility

Cited by in corpus (8)

• Data-Driven Methods for Present and Future Pandemics: Monitoring, Modelling and Managing
• The Role of Asymptomatic Individuals in the COVID-19 Pandemic via Complex Networks
• On node ranking in graphs
• Families of graphs with twin pendent paths and the Braess edge
• On Kemeny's constant and stochastic complement
• Heterogeneous Mean First-Passage Time Scaling in Fractal Media
• A First-Order Gradient Approach for the Connectivity Optimization of Markov Chains
• Screening for an Infectious Disease as a Problem in Stochastic Control