Effective epidemic containment strategy in hypergraphs

Recently, hypergraphs have attracted considerable interest from the research community as a generalization of networks capable of encoding higher-order interactions, which commonly appear in both natural and social systems. Epidemic dynamics in hypergraphs has been studied by using the simplicial susceptible-infected-susceptible ($s$-SIS) model; however, the efficient immunization strategy for epidemics in hypergraphs is not studied despite the importance of the topic in mathematical epidemiology. Here, we propose an immunization strategy that immunizes hyperedges with high simultaneous infection probability (SIP). This strategy can be implemented in general hypergraphs. We also generalize the edge epidemic importance (EI)-based immunization strategy, which is the state of the art in complex networks. However, it does not perform as well as the SIP-based method in hypergraphs despite its high computational cost. We also show that immunizing hyperedges with high H-eigenscore effectively contains the epidemics in uniform hypergraphs. A high SIP of a hyperedge suggests that the hyperedge is a “hotspot” of the epidemic process. Therefore, SIP can be used as a centrality measure to quantify a hyperedge's influence on higher-order dynamics in general hypergraphs. The effectiveness of the immunization strategies suggests the necessity of scientific, data-driven, systematic policy-making for epidemic containment.

Figure 1

Schematic representation of simplicial susceptible-infected-susceptible ($s$-SIS) model. Black dots represent susceptible nodes, red dots represent infected nodes, and the grey area represents hyperedges. The contagion along a hyperedge occurs if and only if exactly one node is susceptible and all the other nodes are infected. If the condition is met, the susceptible node is turned to the infected state with rate ${\beta }_d$, where $d$ is the size of the hyperedge. If the hyperedge is immunized, the contagion through the hyperedge does not occur. Additionally, the recovery process $\mathrm{S}\to \mathrm{I}$ is defined identically to the traditional susceptible-infected-susceptible (SIS) model.

Figure 2

(a) The degree distribution of the 3-uniform hypergraph popularity-similarity optimization ($h$-PSO) model. The mean degree $\langle k\rangle =6$, temperature $T=0.5$, and the parameter $\gamma =3$. The tail of the distribution follows a power law with an exponent of 3. (b) The clustering coefficient of 3-uniform $h$-PSO as a function of the scale parameter $R$. The number of nodes $N=2000$, mean degree $\langle k\rangle =6$, and the temperature $T=0.5$.

Figure 3

Random edge immunization (Random), H-eigenscore (H-ES), EI, and SIP-based strategies tested in various synthetic and empirical networks: (a, e, i) the static model, (b, f, j) clustered power-law network, (c, g, k) an airline network, and (d, h, l) the general relativity collaboration network. Because this is a network (i.e. hypergraph with only size-two hyperedges) the H-eigenscore is identical to the usual eigenscore. (a, b, c, d) The density of infection $\rho$ versus the removed portion of the edges $p$. The recovery rate $\mu =0.2$ and the contagion rate $\beta =0.2$. Efficient immunization strategies usually result in a higher density of infection compared to random immunization for small $p$ but eliminate epidemics with smaller $p_c$. (e, f, g, h) HIT $p_c$, which is the minimally required portion of edges to eliminate the epidemics. The efficient strategies (i.e. H-eigenscore, EI, and SIP-based strategies) exhibit marginal differences in their HITs. To compare the HITs of efficient strategies more thoroughly, we plot the differences between the $p_c$'s of EI and SIP-based strategies from the $p_c$ of the H-eigenscore-based strategy in (i, j, k, l). The SIP-based strategy is often more efficient than EI-based strategy, despite its lower computational cost.

Figure 4

Random hyperedge immunization (Random), H-eigenscore (H-ES), EI, and SIP-based strategies tested in 3-uniform hypergraphs: (a, c) the hypergraph static model and (b, d) the hypergraph popularity-similarity optimization ($h$-PSO) model. (a, b) The density of infection $\rho$ versus the removed portion of the edges $p$. The recovery rate $\mu =0.2$ and the contagion rate $\beta ={\beta }_3=0.2$. The efficient strategies generally exhibit a higher density of infection for small $p$, but herd immunity is achieved at lower $p_c$, which is the minimally required portion of hyperedges that needs to be immunized to eliminate epidemics. (c, d) HIT $p_c$ as a function of contagion rate $\beta ={\beta }_3$. The H-ES and SIP-based strategies outperform the EI-based strategy, despite their lower computational cost.

Figure 5

Random hyperedge immunization (Random) and SIP-based strategy tested in empirical hypergraphs: (a, c, e) the congressional bill cosponsorship (in 2000) hypergraph and (b, d, f) the protein interaction hypergraph. For nonuniform empirical hypergraphs, H-ES cannot be implemented due to the variety of hyperedge sizes, and EI is computationally inefficient due to the large hyperedges. (a, b) The density of infection $\rho$ versus the removed portion of the edges $p$. The recovery rate $\mu =0.2$ and the contagion rate $\beta ={\beta }_d=0.2$ for all hyperedge sizes $d$. The efficient strategies generally exhibit a higher density of infection for small $p$, but herd immunity is achieved at lower HIT $p_c$, which is the minimally required portion of hyperedges that need to be immunized to eliminate the epidemics. (c, d) HIT $p_c$ as a function of the contagion rate $\beta ={\beta }_d$. Efficient epidemic containment is achieved by the SIP-based method with low computational cost. (e, f) The immunization rate of hyperedges with size $d$ plotted for various contagion rates. Small hyperedges are primarily targeted by the immunization strategy especially when $\beta$ is low.