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.
