How heterogeneous networks spread the virus?
This work is common collaboration between P.Holme, F.Ianelli, L.Tupikina and G.Simon (from CRI master program). As the result of this work we also are happy to share with you the common repository
https://github.com/Liyubov/heterogeneous_spreading_on_network
INTRODUCTION TO EPIDEMICS SPREADING
Various natural and human-engineered processes in complex systems, including biological, societal, and technological ones, can be thought of happening at networks. Recently after the COVID19 outbreak, epidemics spreading processes on networks became a center of attention of scientists and people all around the globe with many articles released, to name but few open resources [1] and publications [2,3,7]. One of the most commonly used models of epidemic spreading dynamics are so-called susceptible-infected-susceptible (SIS) and susceptible-infected-recovered (SIR) models [2]. In those, the whole population is split into the compartments of susceptible, infected, or recovered individuals (below in the text, we assume all individuals to be nodes of our network). There are numerous ways to explore properties of infection spreading model on a network, e.g., using numerical simulations [2,3] and analytical methods and mathematical modeling approaches [4]. For models on large networks, we often need to use some other tricks, e.g., to introduce some special local network measures that may help identify influential spreaders in complex networks [5]. Much more challenging is to consider spreading on networks with so-called heterogeneities. By heterogeneities, we mean when some edges or nodes have their speed or ability to spread the infection. In our work, we focus specifically on the case of spreading on networks with such heterogeneous nodes. Such spreading is an important extension of homogeneous epidemics spreading. In particular, we analyzed the disease spreading processes, incorporating heterogeneities in networks, which may be associated with the environment’s physical, epidemiological and socio-economic properties. We assume that an infection is spreading on undirected relatively small networks. In particular, we use some properties of spreading dynamics in heterogeneous networks using the mathematical theory of stochastic processes [9]. In our context, we understand heterogeneity from both topological and dynamical perspectives. We also share and comment on the open code [8], which we developed for simulating epidemics spreading dynamics.
The susceptible-infected-recovered model
First, let us present susceptible-infected-recovered model (SIR) of epidemics spreading. We assume every individual is in one condition concerning the disease: S (susceptible), I (infected), R (recovered). Each node can be in one of those states at each time. S nodes become I with probability (chance) β, when in contact with I nodes, and I nodes become R spontaneously with probability γ. The stationary fraction (in mathematics we call the stationary case when time t goes to infinity) of nodes in the removed (or recovered) state, averaged over many realizations, ρ(β) = R(t=∞)/N is a specific important parameter of the epidemics spreading model itself.
SIR model in heterogeneous case
SIR model in heterogeneous setup is defined as follows. Each node in the beginning of a simulation is given a state: S, I or R. Each node i has value i corresponding to its recovery rate when it is infected. Each edge has its unique transmission rate, also called an infectious rate, when a node is in a susceptible state. Here we focus on a particular SIR model setup when all nodes have the same recovery rates and transmission rates and one heterogeneous node has a different transmission rate i than other nodes surrounding it.
CODE FOR SIMULATIONS OF HETEROGENEOUS SIR MODEL
In our notebook we demonstrate the tools for analysis namely
https://github.com/Liyubov/heterogeneous_spreading_on_network/blob/master/notebooks/heterogeneous_spreading.ipynb
Below we describe in details how to use each function in repository https://github.com/Liyubov/heterogeneous_
spreading_on_network/tree/master/python_code for calculation of network measures connected with the infection
spreading:
1. The code in main file simulates the SIR model on heterogeneous network, where transmission rate on a heterogeneous node is different than on other nodes. One can insert the list of the different heterogeneous nodes you want to put in a network at (one at a time, not all together).
2. In the file “Compute_global_measure.py” we compute general temporal characteristics of infection spreading process, such as
- extinction time: time when the epidemics spreading gets extinct;
- averaged arrival time: arrival time, corresponds to time, when epidemics arrives from node i to node j, averaged
over all nodes in a network;
3. In the file “Compute_local_measure.py” we compute local measures such as
- probability of a node to be infected: chance of a node to be infected in a network, resulted from numerous simulations;
- arrival time of the infection to a node: time, which it takes for the infection to arrive from any node i to a given node j;
- effective distance: a network-based measure that generalizes the concept of physical distance [6].
In the notebook we explain in details about each part of our work, which we separate into several parts:
• generation of random graphs (or networks) for which we run the infection spreading — function create_watts_strogatz_graph(n; k; p)
• general simulation of SIR model — function first_infection(G; listinfected; listrecovered) or create_barabasi_albert_graph(n;m)
• calculation of extinction time of epidemics spreading process — function extinction_time(N; t0; tmax; simtimes; simnodes)
• calculation of arrival times of epidemics spreading process — function arrivaltime(N; t0; tmax; simtimes; simnodes; simactions)
• calculation of probability of each node to be infected after certain time — function proba_be_infected_aftert(N; t0; tmax; simtimes; calculation of the outbreak time, which is time when outbreak happen (outbreak is when maximum number of infected nodes are present at one point) — function outbreaktime(N; t0; tmax; simtimes; simnodes; simactions);
• calculation of the outbreak size — function outbreaksize(N; t0; tmax; simtimes; simnodes; simactions)
• network measure of conditional betweenness centrality, applied speci cally to infection spreading process on a network G — function node_conditionnal_BC(G; firstinfected);
• network measure of effective distance estimated using function effective_distance(G; firstinfected; beta), described [6] and above;
• network layout, such that a node, where infection starts, here noted as central node has a central position — function central_layout(G; centralnode).
RESULTS
Our primary research questions are related to quantifying the results of heterogeneities in networks. First, we investigate to which extent heterogeneities in networks, encoded through node parameters of epidemics spreading, influencing, and controlling disease spreading on a network. Second, this question is closely related to how to dissect heterogeneous node influence from structural (topological) heterogeneities and heterogeneities of epidemics spreading model parameters.
For addressing the first question, we look into quantitative measures, such as arrival times and extinction times of the spreading process. For the second question, we locally estimate measures on a network (such as conditional betweenness centrality) and plot the network using a special circular layout.
We show some results of the simulations, which can be performed with the code we shared in https://github.com/Liyubov/heterogeneous_spreading_on_network/tree/master/python_code.
In Fig. 1 we plot the probability to infect the node and the effective distance for both, homogeneous and heterogeneous
spreading cases. The plots are calculated using proba_be_infected_after_t(N; t0; tmax; simtimes; simnodes; simactions) and effectivedistance() functions.
In Fig. 2 we show the effective distance using analytical formula in for effective distance [6]. The alignment for analytical results for effective distance is much stronger for larger number of nodes N. The plots are calculated using functions effective_distance() and analytical formula for effective distance calculation from [6].
Finally, in Fig. 3 we demonstrate a network, where node sizes are proportional to betweenness and node color is proportional to the probability of infection. This allows us to compare these two quantities. We also introduce a network measure of conditional betweenness centrality, specifically applied to infection spreading process on a network G, which is defined for each node x in respect to some fixed node y, through all paths, which are going through both of those nodes.
General betweenness centrality reflects to which extent a node lies on the shortest paths linking other nodes, Fig. 3, we can see the effect of heterogeneity of spreading, preventing epidemics to take the shortest (geometrically) paths. The plot is calculated using the functions of node_conditionnal_BC(G; firstinfected) and central_layout(G; centralnode).
We also encourage you to look at the Networkx Python library, which explains about each of network measures separately.
References
[1] Submissions to arxiv about COVID19 https://arxiv.org/
[2] P. Holme, “Shadows of the susceptible infectious susceptible immortality transition in small networks”, Phys.Rev. E, 012804 (2015)
[3] V.Colliza, A. Barrat, M. Barthlemy, A. Vespignani, “The role of the airline transportation network in the
prediction and predictability of global epidemics”, PNAS (2003)
[4] P. Holme, L. Tupikina, “Epidemic extinction in networks: insights from the 12 110 smallest graphs”, New J. Phys. 20 113042(2018)(2018)
[5] M. Kitsak, L.K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H.E. Stanley, “Identification of influential spreaders in complex networks”, Nature Physics 6, 888893, (2010)
[6] F. Iannelli, A. Koher, D. Brockmann, P. Hovel, and I. M. Sokolov, Phys. Rev. E 95, 012313 (2017)
[7] L. Ferretti, et al. “Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing”,10.1126 science.abb6936 Science (2020)
[8] code available at https://github.com/Liyubov/heterogeneous_spreading_on_network
[9] S. Redner “A Guide to rst passage time processes”, Cambridge (2002)
