Semidefinite bounds for moment dynamics: Application to epidemics on networks

摘要

In this paper, we analyse the (exact) stochastic dynamics of spreading processes in complex networks in order to design strategies to eradicate the spread. A common approach for analysing the dynamics of stochastic spreading models is to apply first-order moment-closure techniques, such as mean-field approximations. However, these moment-closure techniques do not provide quantitative guarantees on the quality of approximation. In this paper, we propose a general moment-closure technique with quality guarantees based on recent results relating the truncated moment problem with semidefinite programming. As a particular application of our technique, we provide upper and lower bounds on the exact dynamics of the SIS spreading process. We demonstrate the validity of our bounds via numerical simulations of spreading process on complex networks.