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.
 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.
D
The Kemeny constant of a graph can be used to identify and analyse bridges between communities in a graph.
R
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
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
R
Simulations
Extensive simulations
R
blocking of
in blocking
R
super-spreader
super-spreaders"