A note on community-detection (Kemeny) based testing for COVID-19

Yilmaz, Serife; Dudkina, Ekaterina; Bin, Michelangelo; Crisostomi, Emanuele; Ferraro, Pietro; Murray-Smith, Roderick; Parisini, Thomas; Stone, Lewi; Shorten, Robert

The Kemeny constant of a graph can be used to identify and analyse bridges between communities in a graph. 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. Tracing techniques aim at reconstructing past history of contacts, but can face practical limits in an exponential growth of either testing or overly conservative quarantining. We show how this application of graph theory can be conveniently used to efficiently intercept new virus outbreaks, when they are still in their early stage. Simulations provide promising results in early identification and blocking of possible"super-spreader links that transmit disease between different communities.