The Suppression of Epidemic Spreading Through Minimum Dominating Set

The Suppression of Epidemic Spreading Through Minimum Dominating Set

Jie Wang, Lei Zhang, Wenda Zhu, Yuhang Jiang, Wenmin Wu, Xipeng Xu, Dawei Zhao

COVID-19 has infected millions of people, with deaths in more than 200 countries. It is therefore essential to understand the dynamic characteristics of the outbreak and to design effective strategies to restrain the 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 finding 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. 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 appeared, and rapidly immunize the whole network at minimum cost.

2021

control, covid-19, minimum dominating set, epidemic spreading, multiplex network

10.3389/fphy.2020.588513

Epidemiology and Health

Korean Society of Epidemiology

Physics