Moving the epidemic tipping point through topologically targeted social distancing

Abstract

The epidemic threshold of a social system is the ratio of infection and recovery rate above which a disease spreading in it becomes an epidemic. In the absence of pharmaceutical interventions (i.e. vaccines), the only way to control a given disease is to move this threshold by non-pharmaceutical interventions like social distancing, past the epidemic threshold corresponding to the disease, thereby tipping the system from epidemic into a non-epidemic regime. Modeling the disease as a spreading process on a social graph, social distancing can be modeled by removing some of the graphs links. It has been conjectured that the largest eigenvalue of the adjacency matrix of the resulting graph corresponds to the systems epidemic threshold. Here we use a Markov chain Monte Carlo (MCMC) method to study those link removals that do well at reducing the largest eigenvalue of the adjacency matrix. The MCMC method generates samples from the relative canonical network ensemble with a defined expectation value of ${\lambda }_{\text{max}}$ . We call this the "well-controlling network ensemble" (WCNE) and compare its structure to randomly thinned networks with the same link density. We observe that networks in the WCNE tend to be more homogeneous in the degree distribution and use this insight to define two ad-hoc removal strategies, which also substantially reduce the largest eigenvalue. A targeted removal of 80% of links can be as effective as a random removal of 90%, leaving individuals with twice as many contacts. Finally, by simulating epidemic spreading via either an SIS or an SIR model on network ensembles created with different link removal strategies (random, WCNE, or degree-homogenizing), we show that tipping from an epidemic to a non-epidemic state happens at a larger critical ratio between infection rate and recovery rate for WCNE and degree-homogenized networks than for those obtained by random removals.

Fig. 1

Example networks from network ensembles after removing $80\%$ of contacts from an initial BA and RG graph with $N=100$ and $E\approx 900$. a and c The generic contact reductions at $\nu =0$ or, in the other word, they show generic networks with random removed links. b and d WCNE at $\nu =1000$. In all figures nodes with the same color and size have the same degree. To compare WCNE networks, i.e. b and d, with the corresponding generic networks with random removed links in a and c), it is visually clear that WCNE networks have more homogeneous degree distribution as well as more homogeneous component sizes

Fig. 2

MCMC substantially decreases ${\lambda }_{\text{max}}$ at higher inverse genericity $\nu$. a and c and show, respectively, the decrease of ${\lambda }_{\text{max}}$ with MCMC for different initial networks for a range of values of the genericity $\nu$. In all networks the removal rate is $\rho =0.4$. For high genericity, such as $\nu \to 0$, ${\lambda }_{\text{max}}$ fluctuates just around its initial value after link removal (yellow line), while it reaches a low steady state for the smaller genericity (black line). b and d show the average of ${\lambda }_{\text{max}}$ for a range of removal fractions $\rho =\{0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9\}$ and genericities. As it is clear in these figures, in the larger $\nu$, the curve is shifted more downwards, indicating a significant increase in the epidemic threshold${\lambda }_{\text{max}}^{-1}$

Fig. 3

Network measures in the ensembles. For both initial network ensembles (BA and RG), the ensembles after link removal are analyzed. a and b show the degree distributions after removal of 80% of links. d and e show the average number of components after the removal of $\rho$ links. g and h demonstrate the size of the giant component after removal of $90\%$ links

Fig. 4

Top: Successively removing the link with the highest degree product results in networks with a very narrow degree distribution. Bottom: Go through nodes in order of increasing node number and remove any links exceeding the cap $k_{\text{max}}=3$

Fig. 5

The degree-based strategies reduce ${\lambda }_{\text{max}}$ almost as well as MCMC. The reduction is greater for smaller removal ratios but persists even if 90 % of edges are removed

Fig. 6

Decreased ${\lambda }_{\text{max}}$ shifts the epidemic threshold to more infectious values of the disease spreading models’ parameters in both SIR (a) and SIS (b) simulations. This shift persists across removal rates $\rho$ and tends to be larger for larger $\rho$. It also persists for the degree-homogenizing methods. c Shows the smallest value of $\beta /\delta$ for each removal rate $\rho$, for which the cumulative number of infected individuals exceeds 1% using the SIS model. It clearly indicates the shift and verifies that it exists for both ad hoc strategies as well as for the WCNE