Mitigating virus spread through dynamic control of community-based social interactions for infection rate and cost

The emergence of COVID-19 in late 2019 has been accompanied by concerns for unprecedented pressure on public health systems. In order to lessen this pressure and contain the spread of the virus, many countries have adopted strategies, such as social distancing or community interaction restrictions (Flaxman et al. 2020; Chinazzi et al. 2020). It has been argued that social distancing between individuals, by isolation and/or community lockdown, is an effective strategy to decrease infection rate and the number of people affected (Basso et al. 2020; Mayr et al. 2020). Regardless of the effect that such restrictions may have (Bendavid et al. 2021), maintaining social distancing for a long time carries out significant costs in economic and social life, including different aspects such as mental heath, well-being, education, transportation, world trade or manufacturing among others. Thus, imposing social distancing can be a challenging decision for the authorities as they have to assess the trade-off between the benefits of social distancing and its costs (Allen 2022). When making a decision about social distancing some key questions to answer are:In this paper, a society is modelled as a community-based graph, where a community indicates a group of people, a district, a city or a country; a link between a pair of communities, an inter-community link, denotes the relationship between the individuals of the communities. The nodes inside each community denote the individuals in the community and a link between a pair of nodes, an intra-community link, indicates a relationship between two individuals. The weight of the links indicates the extent of the relationships. The question is how to adjust the capacity of each intra-community and inter-community link during the spreading period of a virus to formulate a social distancing strategy that achieves two goals: decrease infection rate and decrease the cost incurred from social distancing. To address this question, the problem of identifying an optimal limitation factor for each link is formulated as an optimization problem. A Multi-Objective Particle Swarm Optimization (MOPSO) algorithm is used to propose a method that finds an optimal solution.

The contributions of the paper are summarized as follows.

The rest of the paper is organized as follows: Sect. 2 reviews the relevant literature. Interaction and epidemic models are described in Sect. 3; some details of MOPSO are also discussed in this section. The problem is formally defined in Sect. 4. Section 5 describes the details of the proposed method. The results of the experimental evaluation are reported in Sect. 6. Finally, Sect. 7 concludes the paper and suggests some future directions.

A number of well-used models exist to understand the diffusion of a virus in a population and predict the number of future infections and/or deaths. Most of these models rely on the popular epidemic model, Susceptible-Infected-Recovered (SIR), initially proposed in Kermack and McKendrick (1927). Describing a Bayesian heterogeneity learning approach, the SIR model is formulated into a hierarchical structure in Hu and Geng (2020). In Goel et al. (2021), a mobility-based variant of the SIR model is introduced to take population distribution and the relationship between different geographical locations into account. The authors in Giordano et al. (2020) consider various stages of infections; they take into account both diagnosed and non-diagnosed infected individuals to account for the role of asymptomatic infection in epidemic spreading. The SIR model is expanded in Calafiore et al. (2020) to propose a time-varying spreading model; this model is applied to understand the changes of rate of infection, death and recovery over time. The interactions between heterogeneous groups of individuals are modelled in Contreras et al. (2020) to propose a multi-group variant of SIR; this model is applied to assess the effectiveness of different public health strategies. An interesting direction to predict infection rate is to analyse the messages exchanged between users in online social networks (Comito 2022; Comito et al. 2018); conversations and social interactions among people about a virus become more frequent when the virus gets more prevalent.

Some research has been conducted to choose good strategies that minimize the spread of a virus. In Bairagi et al. (2020), using location and movement of individuals, a game-theoretic method is proposed to help individuals assess their risk and as a result isolate and/or maintain social distancing. Applying Internet-of-Things technologies, a social distancing detection algorithm is suggested in Ksentini and Brik (2020), which detects and warns people who are not maintaining the minimum recommended social distance. In Hosseini et al. (2020), the epidemic process is modelled as an optimization problem where the goal is to minimize the number of infected countries and slow down worldwide epidemic spread. Other papers, such as Wang et al. (2020), Salathé and Jones (2010), adopt a node immunization strategy to prevent the spread of an epidemic.

Due to the economic costs of social distancing restrictions, there are several studies where cost is considered. The effect of different levels of lockdown (or degree of social distancing restrictions) during an epidemic is analysed in Alvarez et al. (2020), Gonzalez-Eiras and Niepelt (2020); according to their results an optimal level for different time periods during an epidemic may be determined. In Olivier et al. (2020), a predictive model is used to evaluate the impact of varying the level of lockdown and determine an optimal level. The authors in Bosi et al. (2021) focus on an optimal lockdown policy by taking the role of households altruism into account. Acemoglu et al. (2020) determine an optimal level of lockdown which differs for different age-groups (young, middle-aged and old). In Caulkins et al. (2021), the public healthcare system capacity is considered to determine multiple lockdown strategies with different levels and lengths. These papers have a rather static view in their models where the impact of individuals’ travel is not taken into account, something that we consider in our paper.

Individuals travelling (or commuting) between cities or regions may have a significant impact on the spread of the epidemic (Glaeser et al. 2020; Jia et al. 2020). The proliferation of GPS-enabled technologies and location-based social networks can easily provide useful geographic information to model location and mobility patterns of people in a society (Zhao et al. 2016; Stock 2018). In Oum and Wang (2020), a model is presented to analyse the effect of urban traffic congestion on the infection risk and economic costs. The problem of identifying a set of key links between communities to minimize the spread of virus is tackled in Chen et al. (2021). To assess the impact that individuals’ travel may have on spreading a virus, in some studies the relationship between regions is modelled as a graph and the goal is to determine the optimal commuting flow between the regions.

In Birge et al. (2020), a city is modelled as a set of neighbourhoods where each neighbourhood has a number of individuals. Individuals spend a fraction of their time in other neighbourhoods; as they come to contact with individuals from other neighbourhoods, a virus is spread between the neighbourhoods. The goal is to determine the optimal level of lockdown to limit the interaction between each pair of neighbourhoods with minimum costs. Applying linear programming methods, the problem is solved under large and small infection regime scenarios. A similar problem is defined in Fajgelbaum et al. (2020), where commuting locations (such as train stations, workplaces and public places) and the number of commuters between these locations are modelled as a graph. By defining a cost model for the lockdown, the goal is to determine the optimal number of commuters between the locations to curb the spread of a virus with minimum costs. By considering the role of both asymptomatic and symptomatic infected individuals in the spreading process, the problem of identifying an optimal link restriction between communities in order to maintain a trade-off between infection rate and economic costs is discussed in Ma et al. (2020). The research in Birge et al. (2020), Fajgelbaum et al. (2020), Ma et al. (2020) is the closest to our work. The problem formulated in the present paper differs from those defined in Birge et al. (2020), Fajgelbaum et al. (2020), Ma et al. (2020) as, in these papers, only travel of individuals between regions is considered.

In our paper, we model the spread of a virus in two levels (inter- and intra-community) to capture virus propagation between individuals from different regions and also between individuals within the same region. This can lead to an appropriate limitation factor for the links between regions as well as an appropriate level of social distancing restriction within each region; these two may be different. For this propose, the society is modelled as a community-based graph to capture the intra- and inter-community interactions between individuals. The optimal lockdown problem is then defined as a bi-objective optimization problem which considers both the probability of infection and the costs of lockdown. Thanks to the successful Particle Swarm Optimization (PSO) algorithm (Kennedy and Eberhart 1995) that can be used to solve optimization and multi-objective problems (Rahimi et al. 2018; Wang et al. 2019; Cui et al. 2020), PSO is then applied to solve our bi-objective optimization problem under two scenarios: internal-relationship-aware communities where information about the interactions within each community (intra-community interactions) is available, and internal-relationship-agnostic communities where such information is not available. In both scenarios, we assume that information about interactions across communities (inter-community interactions) is available.

Minimizing the spread of a disease is an important issue to mitigate its consequences and impact to a society. Minimizing interaction between people can be an effective way for this goal. Thus, in this paper, we aim to identify a set of critical links to contain the spread of disease over time. Two different containment strategies are adopted in this paper: (i) limit the interaction between a pair of neighbours by imposing limitations to the edge between the pairs; (ii) limit the interaction between a pair of communities by imposing limitations to the inter-community edge between the pairs. In fact, we aim to limit the critical intra-community edges by limiting the time that two neighbours spend together and the critical inter-community edges by limiting the number of individuals travelling between the communities. It is noted that imposing limitations on the edges has some cost. In addition, the edges cannot be limited for a long time, so we dynamically limit and unlimit the edges (i.e. tighten and relax the restrictions) over the spreading period. That is to say, at each timestamp we decide to limit or unlimit a set of edges (intra- and inter-community).

The cost of limitation for each edge depends on its weight. For example, if the time that two friends spend together is long they are more reluctant to be banned from meeting each other; a blanket ban may have a high cost. Thus, suppose that limiting \(\eta _{ij} \%\) of the interaction between two neighbours \(v_i\) and \(v_j\) (connected by the edge \(e^{V}_{ij}\)) for one timestamp costs \(LC^{V}_{ij}= w^{V}_{ij}\cdot \eta _{ij}\). Again, suppose that limiting \(\eta _{ij} \%\) of the interaction between two communities \(c_i\) and \(c_j\) (connected by the edge \(e^{C}_{ij}\)) for one timestamp costs \(LC^{C}_{ij}=w^{C}_{ij}\cdot \eta _{ij}\% \cdot 2 \cdot \alpha\). The weight of each inter-community edge represents the number of commuters in both directions. As each commuter may have \(\alpha\) inter-community neighbours, we consider \(2\cdot \alpha\) to determine the cost of limiting inter-community edges. According to these definitions, every edge can be stated as \(\eta \%\)-limited at each timestamp during the spreading process, where \(\eta\) is the limitation factor of the edge, a value in [0, 1]; if \(\eta =0\) the edge is unlimited, \(0<\eta <1\) the edge is limited and if \(\eta =1\) the edge is completely blocked.

We call this problem Progressive Limitation of Critical Interactions (PLCI). The goal is to choose an optimal \(\eta _{ij}\) for every edge \(e_{ij}\) (intra- and inter-communities) at each timestamp t during the spreading process. Thus, the PLCI problem is defined as: given a society modelled by a graph \(G(V,E^{V},C,E^{C})\) and a set of nodes in contact with infected nodes, the goal is to determine a limitation factor \(\eta _{ij}\) for every edge \(e_{ij}\) at each timestamp t so that the number of infected nodes is minimized with a minimum cost. That is to say, the goal is to find the trade-off between the number of infected individuals and the cost of limitations on the edges. Suppose that the spreading process continues for T timestamps. Then, as a formal definition, the problem aims to determine the limitation factor for every edge at each timestamp \(t=1\ldots T\) to set \(E^{V}(t)\) and \(E^{C}(t)\), where \(w_{ij}(t)=w_{ij}\cdot \eta _{ij}\). The objective functions of the problem in each timestamp t are defined as follows:

The goal of the PLCI problem at each timestamp t is defined as a multi-objective problem in Eq. (4):

The overall framework to address the problem is shown in Algorithm 1. Due to the detection of infected people, a set of exposed individuals who have been in contact with infected nodes is determined as potentially infected individuals in line 1. Edge limitation continues in sequential timestamps ts while there are potentially infected individuals in a society, i.e. \(PT\ne \emptyset\). In line 6, the capacity of the edges is determined and some edges are limited or unlimited according to the infection status in the society. In lines 8–14, the individuals who commute between communities and their temporary neighbours (inter-community neighbours) are determined. A set of potentially infected nodes is randomly determined as infected nodes in line 17. The first iteration of the spreading process is simulated in lines 18–22 where the virus can spread through intra- and inter-community edges. In lines 24–25, the commuted individuals return back to their communities. The second iteration of spreading is simulated in lines 27–31. In lines 33–36, the infected nodes are recovered and the set of nodes who were in contact with them are set to be exposed individuals (potentially infected nodes). This process continues until no potentially infected nodes remain. In the next section, a method to determine the limitation factor of the edges in line 6 of the framework is proposed.

In Sect. 5.1, we propose a method to determine an optimal value for the limitation factor of every edge at each timestamp \(t>0\). For this purpose, the infection probability of each node in each timestamp needs to be calculated. Section 5.2 describes the details on how to calculate the infection probability of each node using two scenarios: internal-relationship-aware and internal-relationship-agnostic.

In this section, the performance of the proposed methods is evaluated. To do so, a set of experiments is carried out and the results obtained by the proposed methods SAEL and SUEL are compared to the simple heuristics described below:

In order to generate a set of networks for evaluation, we apply the Lancichinetti–Fortunato–Radicchi (LFR) benchmark (Lancichinetti et al. 2008), which is used to generate synthetic networks based on: number of nodes |V|, average degree of nodes \(\langle d \rangle\), minimum community size m(C), maximum community size M(C) and mixing parameter \(\mu\). The mixing parameter \(\mu\) defines the expected proportion of edges which connect two nodes in different communities. Two synthetic networks with varying features, SN1 and SN2, are generated. We set \(|V|=200\), \(\langle d \rangle =5\), \(m(C)=20\), \(M(C)=40\) and \(\mu =0.10\) to generate SN1. We set \(|V|=1000\), \(\langle d \rangle =8\), \(m(C)=50\), \(M(C)=100\) and \(\mu =0.12\) to generate SN2. To determine the inter-community edges in SN1 and SN2, we first check for edges connecting any node in community \(C_i\) to any node in community \(C_j\). If there are x such edges, we remove these edges between nodes and we create an inter-community edge between communities \(C_i\) and \(C_j\) with weight x. The characteristics of SN1 and SN2 are shown in Table 1. The table shows the number of nodes (|V|), the number of intra-community edges (\(|E^V|\)), the average weight of the intra-community edges (\(\langle W^V \rangle\)), the number of communities (|C|), the number of inter-community edges (\(|E^C|\)), the average weight of the inter-community edges (\(\langle W^C\rangle\)), the number of nodes in the biggest community (M(C)) and the number of nodes in the smallest community (m(C)). Furthermore, the characteristics of each community, for both SN1 and SN2, are shown in Fig. 2; these characteristics include the number of nodes in the community, density, which is the sum of the weight of edges between the nodes (intra-community edges) within the community, and the weighted degree, which is the sum of the weight of edges between the community and other communities (inter-community edges).

Four different experiments are conducted to assess the performance of the proposed methods.

Each experiment is repeated 50 times with a different initial set of infected nodes selected randomly. For each set, the extended SIR model is independently repeated 100 times to increase confidence in the obtained results. In the first three experiments, we set \(\alpha =3\), which means that each individual commuting from one community to another community has three inter-community neighbours in the destination community. For the parameters \(\omega\) (inertia weight), \(c_1\) and \(c_2\) (learning factors) in the proposed methods (see Algorithm 2), we follow the suggestions in Eberhart and Shi (2000), Shi and Eberhart (1999), Ratnaweera et al. (2004). Thus, the value of \(\omega\) varies from 0.9 to 0.4, the value of \(c_1\) varies from 2.5 to 0.5 and the value of \(c_2\) varies from 0.5 to 2.5. Finally, for the second and third experiments, different values of \(q_1\) and \(q_2\) are used to evaluate the performance of the proposed methods when the objectives may not have the same importance; in experiments one and four, \(q_1\) and \(q_2\) are both set 1.

Minimizing the interaction between individuals and communities is an approach to contain the spread of a virus, however, it comes at a cost. In this paper, a framework to model the spreading process of a virus in intra- and intra-community interactions was proposed. The problem of limiting interactions was defined as a multi-objective problem where the aim is to achieve a trade-off between the number of infected individuals and the cost of limitations. Then, PSO was applied to find an optimal solution of the problem under two different scenarios. The experimental results suggest that the performance of the proposed methods compared favourably to simple heuristics. Future work may focus on modelling the problem using large-scale networks and designing different strategies to determine the limitation factor of each edge. How to model interactions when little information is available or taking into account uncertainty in the interactions can also be an issue for future work. Finally, all individuals in this paper are considered the same (homogeneous population); yet, different individuals may have different levels of health risk. Modelling individuals with a different level of risk and minimizing infection based on the individuals’ level of risk could also be considered.