Unified mean-field framework for susceptible-infected-susceptible epidemics on networks, based on graph partitioning and the isoperimetric inequality

We propose an approximation framework that unifies and generalizes a number of existing mean-field approximation methods for the susceptible-infected-susceptible (SIS) epidemic model on complex networks. We derive the framework, which we call the unified mean-field framework (UMFF), as a set of approximations of the exact Markovian SIS equations. Our main novelty is that we describe the mean-field approximations from the perspective of the isoperimetric problem, which results in bounds on the UMFF approximation error. These new bounds provide insight in the accuracy of existing mean-field methods, such as the N-intertwined mean-field approximation and heterogeneous mean-field method, which are contained by UMFF. Additionally, the isoperimetric inequality relates the UMFF approximation accuracy to the regularity notions of Szemerédi's regularity lemma.

Figure 1

Schematic representation of the relationship between the different variables involved in the UMFF approximation steps.

Figure 2

Example of the transition structure of the SIS process on a four-node network. On the left, a network is shown together with its schematic representation. Sick nodes in the network are colored pink, which is encoded in the schematic representation as pink squares. State transitions are represented by connected squares. Full lines represent bidirectional transitions and dotted lines represent unidirectional transitions. The schematic representation of the reduced network disease state is simply the number of infected nodes in that state. On the right, the transition structure of the SIS process on this four-node network is shown. Already for a small network, the full-state transition structure turns out to be complex. As an illustration of the UMFF approach, the full-state transition structure is simplified to the reduced-state transition structure for a one-partition partitioning $(K=1)$. This partitioning combines all the full states with the same number of infected nodes into a single reduced state. Additionally, the reduced-state transition rates are a combination of the full-state transition rates. Appendix pp2-s2 describes this reduction in more detail.

Figure 3

Schematic of the disease state in a network. The infected and healthy nodes determine two separate partitions separated by the cut set, the set of infective links.

Figure 4

Conceptual diagram depicting the analogy between the UMFF topological approximation (5) and the isoperimetric inequality (21).