Effective distances for epidemics spreading on complex networks

We show that the recently introduced logarithmic metrics used to predict disease arrival times on complex networks are approximations of more general network-based measures derived from random walks theory. Using the daily air-traffic transportation data we perform numerical experiments to compare the infection arrival time with this alternative metric that is obtained by accounting for multiple walks instead of only the most probable path. The comparison with direct simulations reveals a higher correlation compared to the shortest-path approach used previously. In addition our method allows to connect fundamental observables in epidemic spreading with the cumulant-generating function of the hitting time for a Markov chain. Our results provides a general and computationally efficient approach using only algebraic methods.

Figure 1

The global mobility network used in the simulations consisting of $V=3865$ airports and $E=51440$ flights [15].

Figure 2

(a) Circular representation of the global mobility network with vertex colors and size corresponding to its strength $k_i^W$. (b) Normalized weight distribution $\mathcal{P}\left(W\right)\sim W^{-{\gamma }_w}$ with scaling exponent ${\gamma }_w=3.60\pm 0.14$. Inset: Unweighted degree distribution $\mathcal{P}\left(k\right)\sim k^{-{\gamma }_k}$ with scaling exponent ${\gamma }_k=1.79\pm 0.10$. Scaling exponents are obtained using the method presented in Ref. [27].

Figure 3

Correlation of the infection arrival times in days obtained from simulation of (9) with the shortest-path (light blue circles) and the random-walk effective distance (violet squares). The source infected node $i$ is São Paulo Guarulhos International Airport, and each point in the scatter plot corresponds to an airport $j$ in the global mobility network, with size proportional to its strength $k_j^W$. The mobility and epidemiological parameters are respectively $\alpha =0.028{\mathrm{d}}^{-1}, \beta =0.407{\mathrm{d}}^{-1}$, and $\mu =0.271{\mathrm{d}}^{-1}$ resulting in $\delta =1$. The Pearson correlation coefficients are $R_{\text{SP}}^2=0.96$ and $R_{\text{RW}}^2=0.99$.

Figure 4

Distribution of the Pearson coefficient $R^2$ considering all possible infection sources in the global mobility network for same parameters as in Fig. 3.

Figure 5

Correlation of the shortest-path (light blue) and random-walk (violet) approach with the simulations arrival time for the the U.S. airport network used in Ref. [13] (a) and its randomized (Erdős-Rényi) version (c). In (b) and (d) the corresponding networks visualization consisting of $V=500$ nodes and $E=5960$ edges. Parameters as in Fig. 3.

Figure 6

Correlation of the shortest-path (light blue) and random-walk (violet) approach with the simulations arrival time for an unweighted Barabási-Albert network (a) and a two-dimensional lattice embedding (c) both consisting of $V=500$ nodes. In (b) and (d) the corresponding networks visualization. The number of edges is, respectively, $E=998$ and $E=1000$. Parameters as in Fig 3.