Relevance of backtracking paths in recurrent-state epidemic spreading on networks

The understanding of epidemics on networks has greatly benefited from the recent application of message-passing approaches, which allow us to derive exact results for irreversible spreading (i.e., diseases with permanent acquired immunity) in locally treelike topologies. This success has suggested the application of the same approach to recurrent-state epidemics, for which an individual can contract the epidemic and recover repeatedly. The underlying assumption is that backtracking paths (i.e., an individual is reinfected by a neighbor he or she previously infected) do not play a relevant role. In this paper we show that this is not the case for recurrent-state epidemics since the neglect of backtracking paths leads to a formula for the epidemic threshold that is qualitatively incorrect in the large size limit. Moreover, we define a modified recurrent-state dynamics which explicitly forbids direct backtracking events and show that this modification completely upsets the phenomenology.

Figure 1

Scatterplot of the Hashimoto matrix LEV ${\mathrm{\Lambda }}_M^H$ vs the LEV of the adjacency matrix ${\mathrm{\Lambda }}_M^A$ for the 109 real networks described in Ref. [30]. The color of the symbols encodes the network heterogeneity as measured by the factor $〈q^2〉/〈q〉$.

Figure 2

Scatterplot of the inverse numerical SIS threshold estimated for the real networks considered as a function of (a) the QMF prediction ${\mathrm{\Lambda }}_M^A$ and (b) the MP prediction ${\mathrm{\Lambda }}_M^H$. Solid lines represent perfect agreement.

Figure 3

Scatterplot of the Hashimoto matrix LEV ${\mathrm{\Lambda }}_M^H$ vs the LEV of the adjacency matrix ${\mathrm{\Lambda }}_M^A$ for power-law UCM networks of varying size from $N={10}^3$ to $N={10}^7$, averaged over 100 different network realizations for each value of $N$. Error bars are smaller than symbol sizes.

Figure 4

Comparison of the scaling of the inverse numerical SIS threshold ${\lambda }_{c,\mathrm{SIS}}$, the QMF prediction ${\lambda }_{c,\mathrm{QMF}}$, and the MP prediction ${\lambda }_{c,\mathrm{MP}}$ as a function of network size for different values of the degree exponent: (a) $\gamma =2.20$, (b) $\gamma =2.80$, and (c) $\gamma =3.20$.

Figure 5

Illustration of allowed and disallowed events in a time sequence of the NBSIS dynamics. Red nodes are in state I; blue nodes are in state S. Panels are ordered temporally. Solid blue edges are those allowing the transmission of the infection. Red arrows represent infection events. Black dashed arrows do not allow the transmission in the corresponding direction.

Figure 6

(a) Prevalence $\rho \left(t\right)$ as a function of time for $\gamma =3.2$ and various values of $\lambda , N={10}^5$. (b) Same plot for $\lambda =0.3$ and changing network size $N$. (c) Prevalence $\rho \left(t\right)$ as a function of time for $\gamma =2.2$ and various values of $\lambda$, with $N={10}^4$. (d) Same plot for $\lambda =0.3$ and changing network size $N$. Results presented are obtained for a single epidemic run at a given value of $\lambda$ and $N$.

Figure 7

Density of infected nodes $\rho \left(t\right)$ as a function of time for (a) $\gamma =3.2$ and network size $N={10}^5$ and (b) $\gamma =2.2$ with $N={10}^4$. Density of blocked edges $\eta \left(t\right)$ for (c) $\gamma =3.2$ and $N={10}^5$ and (d) $\gamma =2.2$ with $N={10}^4$. Since the blocking of an edge may occur in two different directions, we consider each edge twice and normalize $\eta$, dividing by twice the total number of edges.

Figure 8

Prevalence as a function of time for a SIS process in the karate club network. Data correspond (a) and (c) to the prevalence averaged over all nodes and (b) and (d) to the prevalence of node 29. We compare the results of Monte Carlo simulations, performing averages over all runs and over surviving runs, with the QMF and MP results obtained from integrating the corresponding nonlinear differential equations. SIS parameters are $\mu =0.05$ and (a) and (b) $\beta =0.1$, away from the critical point, and (c) and (d) $\beta =0.01$, close to the critical point. In the initial condition node 0 is infected, and all the others are susceptible. Monte Carlo results are averaged over 1000 independent runs.