This paper investigates the efect of the structure of the contact network on the dynamics of the epidemic outbreak. In particular, we focus on the peak number of critically infected nodes (PCIN), determining the maximum workload of intensive healthcare units that should be kept low when managing an epidemic. As a realistic model and simulation method, we developed a continuous-time Markov chain model, and an open-source available eficient simulation software based on Gillespie's Stochastic Simulation Algorithm (SSA). Virus propagation is compared on random graph models featuring a selected range of complex network topologies: Erdős-Rényi, Watts-Strogatz, Barabási-Albert and complete graph (Clique). Continuous-time Markov chains are used to simulate the infection process. The simulation was performed in networks with 200 nodes and diferent numbers of edges. In addition, we study age- and gender-determined and weighted characteristics of nodes on the PCIN as well as the correlation of macroscopic graph characteristics such as the clustering coeficient and the average shortest path length. The analysis used the data of the demographic distribution of Ukraine as of 2020 and data on mortality from COVID-19 in Ukraine, as of December 16, 2020. It is proved that the deterministic characteristics slightly lower values of critically infected, in small networks for the used dataset. The simulations show that the increase of the average shortest path length is significant on the reduction of the PCIN, whereas other characteristics such as clustering and age distribution, are of lesser importance.
Predicting the dynamics of the spread of infectious diseases in society under diferent circumstances is an urgent scientific and practical social problem. The recent outbreak of the COVID-19 pandemic has increased interest in epidemiology and, as a result, the science of complex networks that can be used to approximate social networks.
It is important to start the fight against the virus as soon as it is detected, but it usually takes a
long time to invent a vaccine[
Another downside of the classical studies is that they focus mainly on the epidemic threshold
(or reproduction number, which is inversely proportional to it), whereas in a real pandemic
other factors deserve more attention when it comes to managing the outbreak: According to
research[
The objective of this paper is to provide a realistic, yet eficient, method for simulation of the
spreading process, and first results on the efects of network topology, with a focus on the peak
number of infected individuals. Instead of asymptotic analysis (such as diferential equations
and mean-field models), we propose using the stochastic simulation algorithm (or Gillespie’s
algorithm[
To solve problems related to the analysis of the dynamics of the spread of infectious diseases in
a population, usually are considering certain generalized models according to which individuals
of such a population are in one of three main possible states: 1) susceptible to infection (S), 2)
infected and able infect others (I) and 3) removed from the list of susceptible and infected due
to the acquisition of immunity or death due to the fatal course of the disease (R). According to
this division, the main epidemiological models are the SI, SIS, and SIR models[
Due to the need to model the spread of COVID-19 among the population, the SIR model was selected as the most appropriate. Although COVID-19 has a certain incubation period, it is dificult to determine, therefore, we consider a person contagious immediately after infection. The possibility of returning the removed persons to a state of susceptibility due to the gradual loss of acquired immunity is also not taken into account. The main parameter is the infection rate . The infection rate depends on the intensity of the contact, its type, and the contagiousness of the virus itself. Since the virus can afect people in diferent ways depending on their gender and age, as well as depending on comorbidities and other factors, in order to take into account these features in the model of disease spread in Ukraine, it was decided to use the demographic distribution as of 2020. (Age structure of the population of Ukraine https: //www.lv.ukrstat.gov.ua/dem/piramid/all.php). Data on the number of infected and mortality as of December 16, 2020, were also used, see operational monitoring of the situation around COVID-19: https://nszu.gov.ua/e-data/dashboard/covid19.
The dynamics of viral spread depend on the network topology, including local characteristics (e.g., local clustering and degrees of nodes) and global characteristics (e.g., eigenvalue spectrum, shortest path characteristics). Real social networks do not have a clear structure but may have certain patterns, so to describe them approximately it is common practice to use random graph models of complex networks, where networks are generated according to certain rules and probability distributions. Within a random graph model, certain properties of networks are typically shared, such as small world or clustering characteristics, and so on. Networks of human contacts are displayed in the form of graphs where an edge connects individuals (nodes) that are in contact with each other. Because human interaction is often bidirectional, we consider here undirected graphs, noting that the simulation methods in this paper can be easily adapted to directed graphs.
The most common network topology discussed in classical epidemiology is that of a Complete
Graph, where each node is connected to every other node. However, in real networks, other
topologies are more common, such as small-world networks, and scale-free networks.
Smallworld models assume a small graph distance between people in a social network (an example is
a rule of "6 handshakes"). It is scale-free networks that are closest to real networks, including
social ones. Scale-free networks are subject to the power law, where the probability () of the
degree of the nodes follows the law ()∼ − . Each of the topologies is described in detail
in [
The Erdős–Rényi graph model is a random graph where links are randomly distributed across a set of nodes. The degree of a node in an ER graph follows a binomial distribution, and not a power law. It is also known, that for > log the network tends to be fully connected, whereas if < the network tends to be fragmented into many isolated components.
The Watts-Strogatz model is a small-world model. The construction of the Watts-Strogatz model begins with a grid in which each node is connected strictly to neighbors, after which each of the edges can reconnect to a randomly selected node with a probability , this process is called reconnection. As a result of reconnection, the average distance between nodes decreases. The Watts-Strogatz model is characterized by high clustering, and also by a small average shortest path which decreases with increasing probability of reconnection of node (to a certain value).
The Barabási–Albert model is a scale-free network with exponent = 3, and it is built on the principle of growth and preferential attachment, that is, at each step a node with edges is added. New nodes are linked to others by preferential attachment to nodes with a probability that is proportional to the degree of the other node. The preferential attachment process leads to the creation of hubs, i. e. a few nodes to which are connected many other nodes with, on average, smaller degrees. These hubs serve as shortcuts for information or diseases spreading through the networks. Therefore the average shortest distance in such networks tends to be small.
For modeling the infection process in this work we use Continuous Time Markov chains
(CTMCs)[
In the CTMC model of the contact process, all rates at which transitions occur between network states are described in a generator matrix = . This matrix is a 2 × 2 matrix and is the rate at which the system changes from network state given it is in state , and (a) Complete graph for n=8 (b) Erdős–Rényi model for = 50, = 50 (c) Watts-Strogatz model for N=10, m=4, p=0.1 (d) Barabási–Albert model for N=50, m=1 = − ∑︀̸= is the rate of leaving state (on the diagonal). Using a state space of size 2 becomes however computationally prohibitive for larger .
In the specific case of simulating the SIR epidemic process, the only non-zero transition rates are those where a single additional node gets infected or where a node that is infected is removed from the network. Let denote the current state and + denote a network state where node ∈ [1, ] is a node that potentially gets infected in addition to the previously infected nodes in state . Then ,+ = ⎧ (), if node is susceptible; ⎪ ⎨∑︀,̸= + , if == + ; ⎪⎩0, if node is not susceptible.
Here is the infection rate of the virus, () is the number of infected neighbors of the vertex in state . The transition time from the state is exponentially distributed: () = {︃ − , if ≥ 0;
0, if < 0
= ∑︀
,̸=
where = . The expected value is given by 1/ , and in the CTMC by 1/. The probability
of transition from state to state , that is is determined by the formula:
and it can be simulated by “roulette wheel” simulation[
We have developed open-source simulation software
https://github.com/YulianKuryliak/EpidemicOutbreak . A slightly modified SIR model was used, in which there are two types of infected - infected and critically infected (ie, people which need medical care). We assume that an infected person becomes contagious immediately after infection. Infectiousness in the case of a normal infection lasts 10 days, after which the person ceases to be considered contagious, according to the SIR model, and is removed from the study network. Based on the current statistics taken from the death statistics in Ukraine from COVID-19 as of December 16, 2020, a certain probability of death due to disease was chosen, namely the weighted average mortality in case of mortality by age and number of people of this age. The weighted probability of death is calculated by the formula: = ∑︀ * + * where - number of men in age range - number of women in age range - probability of death for men of age range - probability of death for women of age range total number of people - age range It is important to predict the occupancy of hospitals, which depends on PCIM. According to the WHO (https://www.who.int/indonesia/news/detail/ 08-03-2020-knowing-the-risk-for-covid-19), there are about 20% of people who develop disease symptoms in the case of COVID-19. Thus, the probability of critical infection will be considered a weighted mortality value, namely, 0.018 increased by 0.2. We will also assume that a critically infected individual spreads the disease within 14 consecutive days, after which they are removed from the network.
Description of input parameters. The experiments used the following parameters. • network size: 200 was selected for all experiments; • infection rate; • network type: can be a complete graph, Erdős–Rényi model, Barabási–Albert model,
Watts-Strogatz model; • type of probability of critical infection: weighted by the number and age for all nodes or separately for each node; • the number of edges (in the case of the Barabási–Albert and Watts-Strogatz models) or the total number of edges in the network (for the Erdős–Rényi model, initial for the node); • term of spread of the disease (in the usual case): set to 10 consecutive days; • period of spread of the disease by critically infected persons: 14 consecutive days are set.
The importance of taking into account the individual age for each of the nodes was tested. For this purpose, 36 simulations were used with the same and diferent probability of critical infection, which has a characteristic age dependence. Since all network topologies are generated regardless of age and gender (in this numerical experiment they were assigned randomly with probabilities corresponding to the demographic distribution of Ukraine in 2020), an experiment was conducted for the worst case of the epidemic - a full graph with 200 nodes, the initial number of patients - 1 and a virus infection rate of 0.002. The number of infected in each of the following points of time is shown in Fig. 3.
When modeling the spread of infection, taking into account the dependence of the probability of infection on the age and sex of each person in the group, or without such a dependence, we obtained two similar curves of the dynamics of spread.
The median values of the number of infected and critically infected persons at each time point were further investigated. For simulations with the same probability of critical infection, the ratio of the number of critically infected to the number of all infected is equal to 0.218 (critically infected / all infected) at any time.
For simulations with a diferentiated probability of critical infection, the average value of the ratio was 0.212, the median value was 0.212, and the standard deviation was 0.013 for the interval 0 ... 45 consecutive days; and a mean of 0.214, a median of 0.213, and a standard deviation of 0.0018 for a period of 10 ... 30 consecutive days (at this time, according to the data obtained from the simulations, a large number of infected people appear).
The curve of critically infected with the individual probability of critical infection is below the curve with the same probability of critical infection. The number of critically infected people varies quantitatively but not qualitatively depending on the individual probability of becoming critically ill, which may be due to fewer older people in the network, as the selected number of nodes is not enough to accurately reproduction the demographic distribution.
For comparison, the most common variants of complex networks with diferent topologies were selected, namely, a random network model Erdős–Rényi, a small-world network model Watts–Strogatz, and a scale-free network model Barabási–Albert. For an objective comparison and compared them with the complete graph. Similar average nodes are selected, and hence the number of edges in the networks.
The values in this and the following tables are averaged for a sample of 100 networks.
As can be seen from the data contained in Table 1, a similar average degree of node network properties (namely, the clustering factor and the average shortest path) difer significantly. To study the influence of parameters, 32. . . 40 simulations were performed for each of the networks.
With the same infection rate for diferent networks, we have a diferent number of infected at each point in time, and therefore a diferent number of critically infected at the same time(Fig.4). As mentioned earlier, the number of infected in the same time is important for predicting hospital occupancy, therefore, experiments were performed for diferent infection rate to estimate the maximum number of co-patients for these rates in each of the networks.
As demonstrated in Fig.5, infection in the complete graph occurs much faster than in other models. Infection in the Erdős–Rényi model occurs faster than in the Watts-Strogatz model, but the Erdős–Rényi model has an asymptote close to 190 nodes because there are nodes that are not part of the giant cluster. Infection in the Barabási–Albert model occurs faster than in the Erdős–Rényi model.
According to Table 1, the Barabási–Albert model has a lower mean shortest distance and an average clustering factor. The Erdős–Rényi model has a higher mean shortest distance from the Barabási–Albert model, but a lower one than the Watts-Strogatz model, and the lowest clustering coeficient. The Watts-Strogatz model has the highest clustering coeficient and the average shortest distance.
Based on the simulation results and the data from Table 1, it can be concluded that for virus spread in networks with a similar average node level, the average shortest distance has a much greater efect on the virus spread rate than the clustering coefitient.
Since the average values of the number of contacts per person are often used, it is worth paying attention to the random Erdős–Rényi model. It was compared with the Barabási–Albert model, which is closer to real networks. And also because these models have a similar average shortest distance. According to the data shown in Tables 2 and 3, the networks generated according to the model have significantly higher Barabási–Albert clustering coeficients than randomly generated networks as predicted by the Erdős–Rényi model.
In Fig. 6 it can be seen that for arbitrarily large virus infectivity, the curves for 200 and 400 edges have asymptotes of about 150 and 190 simultaneously infected nodes. This is due to the detached vertices from the giant component. Therefore, such a model should not be used if it is important to connect all nodes to a giant cluster.
The Barabási–Albert model is a better network option for a small number of edges because, unlike the Erdős–Rényi network, it cannot contain unconnected nodes to a giant cluster. With the same number of edges, the Barabási–Albert model has a higher average of the shortest distance at a small average degree of the node, so the virus in such a network spreads faster.
With a large number of edges in the network, the average shortest distance between nodes decreases, so the diference in the spread of the virus in the Erdős–Rényi and Barabási–Albert networks is minimized.
Although the Barabási–Albert model has higher clustering coeficients, as can be seen from Fig. 6 and Fig. 7, the diference in virus spread at a similar mean shortest distance is insignificant, and therefore the clustering coeficients do not significantly afect the PCIN.
An epidemic outbreak has been simulated in complex networks generated according to models such as the Erdős–Rényi random model, the Watts-Strogatz small-world model, the Barabási–Albert scale-free model, and the complete graph using continuous Markov chains and eficient stochastic simulation techniques for computing their stochastic trajectories.
The importance of taking into account individual node characteristics is analyzed, and it is proved that they are not very important for large networks and weighted values can be used, but in small networks, it is dificult to maintain demographic distribution, so it is better to apply individual node characteristics when they are important.
It has been found that the number of infected at the same time(ie, peak values) and, consequently, the number of critically infected people, depends on the rate of virus transmission on the network, which determines the workload of hospitals, so it is important to take quarantine measures to reduce the height of this peak (PCIN).
The rate of virus spread changes at the same infection rate and average node level for diferent network models. The virus was found to spread fastest in the Barabási–Albert scale-free model, slower in the Erdős–Rényi random model, and slowest in the Watts-Strogatz small-world model. This supports the hypothesis that the speed of virus spread increases with decreasing average shortest distance. In the example of the Erdős–Rényi, and Barabási–Albert models, it is shown that at a similar mean shortest distance between nodes, the clustering coeficient has a negligible efect on the peak value of infected nodes.
Based on this finding, it is obvious that to slow down the spread of the virus, and as a consequence, to reduce the PCIN, it is necessary to increase the average shortest distance, which is provided by mass quarantine measures and also by travel restrictions and close monitoring of network hubs (e.g., individuals or groups of individuals that have many contacts to diferent parts of the network).
Michael Emmerich acknowledges funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement Nr. 823866. 6. References