The Suppression of Epidemic Spreading Through Minimum Dominating Set

The COVID-19 has infected millions of people and lead to death in more than 200 countries. Thus it is essential to understand the dynamical characteristics of epidemic outbreaks and design effective strategies to restrain large-scale spread of the epidemic. In this paper, we present a novel framework to depress the epidemic spreading by leveraging the decentralized dissemination of information. The framework is equivalent to find a special minimum dominating set for a duplex network which is a general dominating set for one layer and a connected dominating set for another layer. By using the spin glass and message passing theory, we present a belief-propagation-guided decimation (BPD) algorithm to construct the special minimum dominating set. As a consequence, we could immediately recognize the epidemic as soon as it appears, and rapidly immunize the whole network with the minimum cost.