Lumping of degree-based mean-field and pair-approximation equations for multistate contact processes

Contact processes form a large and highly interesting class of dynamic processes on networks, including epidemic and information-spreading networks. While devising stochastic models of such processes is relatively easy, analyzing them is very challenging from a computational point of view, particularly for large networks appearing in real applications. One strategy to reduce the complexity of their analysis is to rely on approximations, often in terms of a set of differential equations capturing the evolution of a random node, distinguishing nodes with different topological contexts (i.e., different degrees of different neighborhoods), such as degree-based mean-field (DBMF), approximate-master-equation (AME), or pair-approximation (PA) approaches. The number of differential equations so obtained is typically proportional to the maximum degree $k_{\max }$ of the network, which is much smaller than the size of the master equation of the underlying stochastic model, yet numerically solving these equations can still be problematic for large $k_{\max }$. In this paper, we consider AME and PA, extended to cope with multiple local states, and we provide an aggregation procedure that clusters together nodes having similar degrees, treating those in the same cluster as indistinguishable, thus reducing the number of equations while preserving an accurate description of global observables of interest. We also provide an automatic way to build such equations and to identify a small number of degree clusters that give accurate results. The method is tested on several case studies, where it shows a high level of compression and a reduction of computational time of several orders of magnitude for large networks, with minimal loss in accuracy.

Figure 1

Independent rule $R_{I,i}$ changes a node's state $r_i$ to $p_i.$

Figure 2

Contact rule $R_{C,j}$ changes the state $r_{j_1}$ of a node to state $p_{j_1}$, whereas the state $r_{j_2}=p_{j_2}$ of the other node stays the same.

Figure 3

SIR model: Total fraction of infected $\left(I\right)$, susceptible $\left(S\right)$, and recovered $\left(R\right)$ nodes based on the original (solid lines) vs the lumped (dashed lines) DBMF (a) and PA (c) equations for a power law network with $k_{\max }={10}^3,P\left(k\right)\propto k^{-2.4}$. The maximum error $\epsilon \left(n\right)$ between the full and the aggregated equations w.r.t. the number of bins ($★$) and the maximum difference $F\left(n\right)$ between the aggregated solutions for two consecutive bin numbers ($\circ$) are shown for the DBMF (b) and the PA (d) lumping, respectively.

Figure 4

SIR model: (a) Total fraction of infected $\left(I\right)$, susceptible $\left(S\right)$, and recovered $\left(R\right)$ nodes based on the original (solid lines) vs the lumped (dashed lines) PA equations for a uniform network with $k_{\max }=500,P\left(k\right)=1/k_{\max }.$ (b) The maximum error $\epsilon \left(n\right)$ between the full and the aggregated equations w.r.t.  the number of bins ($★$) and the maximum difference $F\left(n\right)$ between the aggregated solutions for two consecutive bin numbers ($\circ$) for the PA lumping.

Figure 5

SIR model: The number of bins needed for an approximation error of at most $3\times {10}^{-3}$ for the solution of the DBMF and PA equations and for varying $k_{\max }$ (a), and the gain ratio of the computation times $T_{\mathrm{full}}/T_{\mathrm{lumped}}$ of lumped DBMF and PA equations for different $k_{\max }$ (b).

Figure 6

Rumor spreading model: Total fraction of ignorant $\left(I\right)$, spreaders $\left(S\right)$ and stiflers $\left(R\right)$ in a power law network with $k_{\max }=500$ for the original DBMF (a) and PA (c) equations (solid lines) and solution of the corresponding lumped equations (dashed lines). $★$: The running time of the aggregated equations w.r.t. the number of bins used for DBMF (b) and PA (d).

Figure 7

SIIIR model: Total fraction of infected $\left(I\right),\left(II\right),\left(III\right)$ nodes of phases $I,II,III$, respectively, susceptible $\left(S\right)$, and recovered $\left(R\right)$ nodes in a power law network with $k_{\max }=100,P\left(k\right)\propto k^{-2.5}$. The solid lines show the solution of the original DBMF (a) and PA (b) equations, and the dashed lines the solution of the corresponding lumped DBMF (a) and PA (b) equations.

Figure 8

Total fraction of infected $\left(I\right)$, susceptible $\left(S\right)$ and recovered $\left(R\right)$ nodes of the SIR model in a power law network with (a) $k_{\max }={10}^2,P\left(k\right)\propto k^{-2.5}$; (b) $k_{\max }={10}^3,P\left(k\right)\propto k^{-1.14}$; (c) $k_{\max }={10}^5,P\left(k\right)\propto k^{-0.75}$; (d) $k_{\max }={10}^6,P\left(k\right)\propto k^{-0.69}$. The dense lines show the solution of the original DBMF equations, and the dashed lines the solution of the lumped DBMF equations.

Figure 9

The error $\epsilon \left(n\right)$ for $n=17$ for the PA lumped equations considering different initial conditions.