  The ongoing COVID-19 pandemic is the first epidemic in human history in which
digital contact-tracing has been deployed at a global scale. Tracking and
quarantining all the contacts of individuals who test positive to a virus can
help slowing-down an epidemic, but the impact of contact-tracing is severely
limited by the generally low adoption of contact-tracing apps in the
population. We derive here an analytical expression for the effectiveness of
contact-tracing app installation strategies in a SIR model on a given contact
graph. We propose a decentralised heuristic to improve the effectiveness of
contact tracing under fixed adoption rates, which targets a set of individuals
to install contact-tracing apps, and can be easily implemented. Simulations on
a large number of real-world contact networks confirm that this heuristic
represents a feasible alternative to the current state of the art.
