Predicting the Speed of Epidemics Spreading in Networks

Variational kinetic clustering of complex networks

Efficiently identifying the most important communities and key transition nodes in weighted and unweighted networks is a prevalent problem in a wide range of disciplines. Here, we focus on the optimal clustering using variational kinetic parameters, linked to Markov processes defined on the underlying networks, namely, the slowest relaxation time and the Kemeny constant. We derive novel relations in terms of mean first passage times for optimizing clustering via the Kemeny constant and show that the optimal clustering boundaries have equal round-trip times to the clusters they separate. We also propose an efficient method that first projects the network nodes onto a 1D reaction coordinate and subsequently performs a variational boundary search using a parallel tempering algorithm, where the variational kinetic parameters act as an energy function to be extremized. We find that maximization of the Kemeny constant is effective in detecting communities, while the slowest relaxation time allows for detection of transition nodes. We demonstrate the validity of our method on several test systems, including synthetic networks generated from the stochastic block model and real world networks (Santa Fe Institute collaboration network, a network of co-purchased political books, and a street network of multiple cities in Luxembourg). Our approach is compared with existing clustering algorithms based on modularity and the robust Perron cluster analysis, and the identified transition nodes are compared with different notions of node centrality.

Front propagation in a spatial system of weakly interacting networks

We consider the spread of epidemic in a spatial metapopulation system consisting of weakly interacting patches. Each local patch is represented by a network with a certain node degree distribution and individuals can migrate between neighboring patches. Stochastic particle simulations of the SIR model show that after a short transient, the spatial spread of epidemic has a form of a propagating front. A theoretical analysis shows that the speed of front propagation depends on the effective diffusion coefficient and on the local proliferation rate similarly to fronts described by the Fisher-Kolmogorov equation. To determine the speed of front propagation, first, the early-time dynamics in a local patch is computed analytically by employing degree based approximation for the case of a constant disease duration. The resulting delay differential equation is solved for early times to obtain the local growth exponent. Next, the reaction diffusion equation is derived from the effective master equation and the effective diffusion coefficient and the overall proliferation rate are determined. Finally, the fourth order derivative in the reaction diffusion equation is taken into account to obtain the discrete correction to the front propagation speed. The analytical results are in a good agreement with the results of stochastic particle simulations.

Impact of contact rate on epidemic spreading in complex networks

Abstract

Contact reduction is an effective strategy to mitigate the spreading of epidemic. However, the existing reaction-diffusion equations for infectious disease are unable to characterize this effect. Thus, we here propose an extended susceptible-infected-recovered model by incorporating contact rate into the standard SIR model, and concentrate on investigating its impact on epidemic transmission. We analytically derive the epidemic thresholds on homogeneous and heterogeneous networks, respectively. The effects of contact rate on spreading speed, scale and outbreak threshold are explored on ER and SF networks. Simulations results show that epidemic dissemination is significantly mitigated when contact rate is reduced. Importantly, epidemic spreads faster on heterogeneous networks while broader on homogeneous networks, and the outbreak thresholds of the former are smaller.

Graphical abstract

Logistic growth on networks: Exact solutions for the susceptible-infected model

The susceptible-infected (SI) model is the most basic of all compartmental models used to describe the spreading of information through a population. Despite its apparent simplicity, the analytic solution of this model on networks is still lacking. We address this problem here using a novel formulation inspired by the mathematical treatment of many-body quantum systems. This allows us to organize the time-dependent expectation values for the state of individual nodes in terms of contributions from subgraphs of the network. We compute these contributions systematically and find a set of symmetry relations among subgraphs of differing topologies. We use our novel approach to compute the spreading of information on three different sample networks. The exact solution, which matches with Monte Carlo simulations, visibly departs from the mean-field results.

Approximating nonbacktracking centrality and localization phenomena in large networks

Message-passing theories have proved to be invaluable tools in studying percolation, nonrecurrent epidemics, and similar dynamical processes on real-world networks. At the heart of the message-passing method is the nonbacktracking matrix, whose largest eigenvalue, the corresponding eigenvector, and the closely related nonbacktracking centrality play a central role in determining how the given dynamical model behaves. Here we propose a degree-class-based method to approximate these quantities using a smaller matrix related to the joint degree-degree distribution of neighboring nodes. Our findings suggest that in most networks, degree-degree correlations beyond nearest neighbor are actually not strong, and our first-order description already results in accurate estimates, particularly when message-passing itself is a good approximation to the original model in question, that is, when the number of short cycles in the network is sufficiently low. We show that localization of the nonbacktracking centrality is also captured well by our scheme, particularly in large networks. Our method provides an alternative to working with the full nonbacktracking matrix in very large networks where this may not be possible due to memory limitations.

Modeling and controlling the spread of epidemic with various social and economic scenarios

We propose a dynamical model for describing the spread of epidemics. This model is an extension of the SIQR (susceptible-infected-quarantined-recovered) and SIRP (susceptible-infected-recovered-pathogen) models used earlier to describe various scenarios of epidemic spreading. As compared to the basic SIR model, our model takes into account two possible routes of contagion transmission: direct from the infected compartment to the susceptible compartment and indirect via some intermediate medium or fomites. Transmission rates are estimated in terms of average distances between the individuals in selected social environments and characteristic time spans for which the individuals stay in each of these environments. We also introduce a collective economic resource associated with the average amount of money or income per individual to describe the socioeconomic interplay between the spreading process and the resource available to infected individuals. The epidemic-resource coupling is supposed to be of activation type, with the recovery rate governed by the Arrhenius-like law. Our model brings an advantage of building various control strategies to mitigate the effect of epidemic and can be applied, in particular, to modeling the spread of COVID-19.

A toy model for the epidemic-driven collapse in a system with limited economic resource

ABSTRACT

Based on a toy model for a trivial socioeconomic system, we demonstrate that the activation-type mechanism of the epidemic-resource coupling can lead to the collapsing effect opposite to thermal explosion. We exploit a SIS-like (susceptible-infected-susceptible) model coupled with the dynamics of average economic resource for a group of active economic agents. The recovery rate of infected individuals is supposed to obey the Arrhenius-like law, resulting in a mutual negative feedback between the number of active agents and resource acquisition. The economic resource is associated with the average amount of money or income per agent and formally corresponds to the effective market temperature of agents, with their income distribution obeying the Boltzmann-Gibbs statistics. A characteristic level of resource consumption is associated with activation energy. We show that the phase portrait of the system features a collapse phase, in addition to the well-known disease-free and endemic phases. The epidemic intensified by the increasing resource deficit can ultimately drive the system to a collapse at nonzero activation energy because of limited resource. We briefly discuss several collapse mitigation strategies involving either financial instruments like subsidies or social regulations like quarantine.

GRAPHIC ABSTRACT

Model-free hidden geometry of complex networks

The fundamental idea of embedding a network in a metric space is rooted in the principle of proximity preservation. Nodes are mapped into points of the space with pairwise distance that reflects their proximity in the network. Popular methods employed in network embedding either rely on implicit approximations of the principle of proximity preservation or implement it by enforcing the geometry of the embedding space, thus hindering geometric properties that networks may spontaneously exhibit. Here we take advantage of a model-free embedding method explicitly devised for preserving pairwise proximity and characterize the geometry emerging from the mapping of several networks, both real and synthetic. We show that the learned embedding has simple and intuitive interpretations: the distance of a node from the geometric center is representative for its closeness centrality, and the relative positions of nodes reflect the community structure of the network. Proximity can be preserved in relatively low-dimensional embedding spaces, and the hidden geometry displays optimal performance in guiding greedy navigation regardless of the specific network topology. We finally show that the mapping provides a natural description of contagion processes on networks, with complex spatiotemporal patterns represented by waves propagating from the geometric center to the periphery. The findings deepen our understanding of the model-free hidden geometry of complex networks.

An overview of epidemic models with phase transitions to absorbing states running on top of complex networks

Dynamical systems running on the top of complex networks have been extensively investigated for decades. But this topic still remains among the most relevant issues in complex network theory due to its range of applicability. The contact process (CP) and the susceptible-infected-susceptible (SIS) model are used quite often to describe epidemic dynamics. Despite their simplicity, these models are robust to predict the kernel of real situations. In this work, we review concisely both processes that are well-known and very applied examples of models that exhibit absorbing-state phase transitions. In the epidemic scenario, individuals can be infected or susceptible. A phase transition between a disease-free (absorbing) state and an active stationary phase (where a fraction of the population is infected) are separated by an epidemic threshold. For the SIS model, the central issue is to determine this epidemic threshold on heterogeneous networks. For the CP model, the main interest is to relate critical exponents with statistical properties of the network.

Topological Determinants of Perturbation Spreading in Networks

Spreading phenomena essentially underlie the dynamics of various natural and technological networked systems, yet how spatiotemporal propagation patterns emerge from such networks remains largely unknown. Here we propose a novel approach that reveals universal features determining the spreading dynamics in diffusively coupled networks and disentangles them from factors that are system specific. In particular, we first analytically identify a purely topological factor encoding the interaction structure and strength, and second, numerically estimate a master function characterizing the universal scaling of the perturbation arrival times across topologically different networks. The proposed approach thereby provides intuitive insights into complex propagation patterns as well as accurate predictions for the perturbation arrival times. The approach readily generalizes to a wide range of networked systems with diffusive couplings and may contribute to assess the risks of transient influences of ubiquitous perturbations in real-world systems.

Heterogeneous node responses to multi-type epidemics on networks

Having knowledge of the contact network over which an infection is spreading opens the possibility of making individualized predictions for the likelihood of different nodes to become infected. When multiple infective strains attempt to spread simultaneously we may further ask which strain, or strains, are most likely to infect a particular node. In this article we investigate the heterogeneity in likely outcomes for different nodes in two models of multi-type epidemic spreading processes. For models allowing co-infection we derive message-passing equations whose solution captures how the likelihood of a given node receiving a particular infection depends on both the position of the node in the network and the interaction between the infection types. For models of competing epidemics in which co-infection is impossible, a more complicated analysis leads to the simpler result that node vulnerability factorizes into a contribution from the network topology and a contribution from the infection parameters.

Modelling Excess Mortality in Covid-19-Like Epidemics

We develop an agent-based model to assess the cumulative number of deaths during hypothetical Covid-19-like epidemics for various non-pharmaceutical intervention strategies. The model simulates three interrelated stochastic processes: epidemic spreading, availability of respiratory ventilators and changes in death statistics. We consider local and non-local modes of disease transmission. The first simulates transmission through social contacts in the vicinity of the place of residence while the second through social contacts in public places: schools, hospitals, airports, etc., where many people meet, who live in remote geographic locations. Epidemic spreading is modelled as a discrete-time stochastic process on random geometric networks. We use the Monte-Carlo method in the simulations. The following assumptions are made. The basic reproduction number is R0=2.5 and the infectious period lasts approximately ten days. Infections lead to severe acute respiratory syndrome in about one percent of cases, which are likely to lead to respiratory default and death, unless the patient receives an appropriate medical treatment. The healthcare system capacity is simulated by the availability of respiratory ventilators or intensive care beds. Some parameters of the model, like mortality rates or the number of respiratory ventilators per 100,000 inhabitants, are chosen to simulate the real values for the USA and Poland. In the simulations we compare 'do-nothing' strategy with mitigation strategies based on social distancing and reducing social mixing. We study epidemics in the pre-vacine era, where immunity is obtained only by infection. The model applies only to epidemics for which reinfections are rare and can be neglected. The results of the simulations show that strategies that slow the development of an epidemic too much in the early stages do not significantly reduce the overall number of deaths in the long term, but increase the duration of the epidemic. In particular, a hybrid strategy where lockdown is held for some time and is then completely released, is inefficient.

Heterogeneity in outcomes of repeated instances of percolation experiments

We investigate the heterogeneity of outcomes of repeated instances of percolation experiments in complex networks using a message-passing approach to evaluate heterogeneous, node-dependent probabilities of belonging to the giant or percolating cluster, i.e., the set of mutually connected nodes whose size scales linearly with the size of the system. We evaluate these both for large finite single instances and for synthetic networks in the configuration model class in the thermodynamic limit. For the latter, we consider both Erdős-Rényi and scale-free networks as examples of networks with narrow and broad degree distributions, respectively. For real-world networks we use an undirected version of a Gnutella peer-to-peer file-sharing network with N=62568 nodes as an example. We derive the theory for multiple instances of both uncorrelated and correlated percolation processes. For the uncorrelated case, we also obtain a closed-form approximation for the large mean degree limit of Erdős-Rényi networks.

Data-driven study of the COVID-19 pandemic via age-structured modelling and prediction of the health system failure in Brazil amid diverse intervention strategies

In this work we propose a data-driven age-structured census-based SIRD-like epidemiological model capable of forecasting the spread of COVID-19 in Brazil. We model the current scenario of closed schools and universities, social distancing of people above sixty years old and voluntary home quarantine to show that it is still not enough to protect the health system by explicitly computing the demand for hospital intensive care units. We also show that an urgent intense quarantine might be the only solution to avoid the collapse of the health system and, consequently, to minimize the quantity of deaths. On the other hand, we demonstrate that the relaxation of the already imposed control measures in the next days would be catastrophic.

Data-driven study of the COVID-19 pandemic via age-structured modelling and prediction of the health system failure in Brazil amid diverse intervention strategies

In this work we propose a data-driven age-structured census-based SIRD-like epidemiological model capable of forecasting the spread of COVID-19 in Brazil. We model the current scenario of closed schools and universities, social distancing of people above sixty years old and voluntary home quarantine to show that it is still not enough to protect the health system by explicitly computing the demand for hospital intensive care units. We also show that an urgent intense quarantine might be the only solution to avoid the collapse of the health system and, consequently, to minimize the quantity of deaths. On the other hand, we demonstrate that the relaxation of the already imposed control measures in the next days would be catastrophic.

Predicting the Speed of Epidemics Spreading in Networks

Global transport and communication networks enable information, ideas, and infectious diseases to now spread at speeds far beyond what has historically been possible. To effectively monitor, design, or intervene in such epidemic-like processes, there is a need to predict the speed of a particular contagion in a particular network, and to distinguish between nodes that are more likely to become infected sooner or later during an outbreak. Here, we study these quantities using a message-passing approach to derive simple and effective predictions that are validated against epidemic simulations on a variety of real-world networks with good agreement. In addition to individualized predictions for different nodes, we find an overall sudden transition from low density to almost full network saturation as the contagion progresses in time. Our theory is developed and explained in the setting of simple contagions on treelike networks, but we are also able to show how the method extends remarkably well to complex contagions and highly clustered networks.