Kemeny-based testing for COVID-19

PLoS One. 2020 Nov 19;15(11):e0242401. doi: 10.1371/journal.pone.0242401. eCollection 2020.

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 value of the Kemeny constant in the new graph that is obtained when a node is removed from the original 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 the possible 'super-spreaders' links that transmit disease between different communities.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Betacoronavirus
  • COVID-19
  • COVID-19 Testing
  • Clinical Laboratory Techniques
  • Contact Tracing*
  • Coronavirus Infections / diagnosis*
  • Coronavirus Infections / transmission*
  • Humans
  • Models, Theoretical
  • Pandemics
  • Pneumonia, Viral / diagnosis*
  • Pneumonia, Viral / transmission*
  • SARS-CoV-2

Grants and funding

Funding for this study was provided by the following organizations in the form of grants: the Engineering and Physical Sciences Research Council (EPSRC), grant EP/R018634/1, Closed-loop Data Science, awarded to RMS; the European Union’s Horizon 2020 Research and Innovation Programme, Grant Agreement No 739551 (KIOS CoE), awarded to MB and TP; Science Foundation Ireland, grant 16/IA/4610, awarded to RS; and the EPSRC, grant EP/V018450/1, awarded to RS, RMS, and TP.