We extend the N-intertwined mean-field approximation (NIMFA) for the susceptible-infectious-susceptible (SIS) epidemiological process to time-varying networks. Processes on time-varying networks are often analyzed under the assumption that the process and network evolution happen on different timescales. This approximation is called timescale separation. We investigate timescale separation between disease spreading and topology updates of the network. We introduce the transition times T(r) and T¯(r) as the boundaries between the intermediate regime and the annealed (fast changing network) and quenched (static network) regimes, respectively, for a fixed accuracy tolerance r. By analyzing the convergence of static NIMFA processes, we analytically derive upper and lower bounds for T¯(r). Our results provide insights and bounds on the time of convergence to the steady state of the static NIMFA SIS process. We show that, under our assumptions, the upper-transition time T¯(r) is almost entirely determined by the basic reproduction number R0 of the network. The value of the upper-transition time T¯(r) around the epidemic threshold is large, which agrees with the current understanding that some real-world epidemics cannot be approximated with the aforementioned timescale separation.

@en

We analyze continuous-time Markovian ϵ-SIS epidemics with self-infections on the complete graph. The majority of the graphs are analytically intractable, but many physical features of the ϵ-SIS process observed in the complete graph can occur in any other graph. In this work, we illustrate that the timescales of the ϵ-SIS process are related to the eigenvalues of the tridiagonal matrix of the SIS Markov chain. We provide a detailed analysis of all eigenvalues and illustrate that the eigenvalues show staircases, which are caused by the nearly degenerate (but strictly distinct) pairs of eigenvalues. We also illustrate that the ratio between the second-largest and third-largest eigenvalue is a good indicator of metastability in the ϵ-SIS process. Additionally, we show that the epidemic threshold of the Markovian ϵ-SIS process can be accurately approximated by the effective infection rate for which the third-largest eigenvalue of the transition matrix is the smallest. Finally, we derive the exact mean-field solution for the ϵ-SIS process on the complete graph, and we show that the mean-field approximation does not correctly represent the metastable behavior of Markovian ϵ-SIS epidemics.

@en

During the outbreak of a virus, perhaps the greatest concern is the future evolution of the epidemic: How many people will be infected and which regions will be affected the most? The accurate prediction of an epidemic enables targeted disease countermeasures (e.g., allocating medical staff and quarantining). But when can we trust the prediction of an epidemic to be accurate? In this work we consider susceptible-infected-susceptible (SIS) and susceptible-infected-removed (SIR) epidemics on networks with time-invariant spreading parameters. (For time-varying spreading parameters, our results correspond to an optimistic scenario for the predictability of epidemics.) Our contribution is twofold. First, accurate long-term predictions of epidemics are possible only after the peak rate of new infections. Hence, before the peak, only short-term predictions are reliable. Second, we define an exponential growth metric, which quantifies the predictability of an epidemic. In particular, even without knowing the future evolution of the epidemic, the growth metric allows us to compare the predictability of an epidemic at different points in time. Our results are an important step towards understanding when and why epidemics can be predicted reliably.

@en

A network consists of two interdependent parts: the network topology or graph, consisting of the links between nodes and the network dynamics, specified by some governing equations. A crucial challenge is the prediction of dynamics on networks, such as forecasting the spread of an infectious disease on a human contact network. Unfortunately, an accurate prediction of the dynamics seems hardly feasible, because the network is often complicated and unknown. In this work, given past observations of the dynamics on a fixed graph, we show the contrary: Even without knowing the network topology, we can predict the dynamics. Specifically, for a general class of deterministic governing equations, we propose a two-step prediction algorithm. First, we obtain a surrogate network by fitting past observations of every nodal state to the dynamical model. Second, we iterate the governing equations on the surrogate network to predict the dynamics. Surprisingly, even though there is no similarity between the surrogate topology and the true topology, the predictions are accurate, for a considerable prediction time horizon, for a broad range of observation times, and in the presence of a reasonable noise level. The true topology is not needed for predicting dynamics on networks, since the dynamics evolve in a subspace of astonishingly low dimension compared to the size and heterogeneity of the graph. Our results constitute a fresh perspective on the broad field of nonlinear dynamics on complex networks.

@en

How temporal modulations in functional interactions are shaped by the underlying anatomical connections remains an open question. Here, we analyse the role of structural eigenmodes, in the formation and dissolution of temporally evolving functional brain networks using resting-state magnetoencephalography and diffusion magnetic resonance imaging data at the individual subject level. Our results show that even at short timescales, phase and amplitude connectivity can partly be expressed by structural eigenmodes, but hardly by direct structural connections. Albeit a stronger relationship was found between structural eigenmodes and time-resolved amplitude connectivity. Time-resolved connectivity for both phase and amplitude was mostly characterised by a stationary process, superimposed with very brief periods that showed deviations from this stationary process. For these brief periods, dynamic network states were extracted that showed different expressions of eigenmodes. Furthermore, the eigenmode expression was related to overall cognitive performance and co-occurred with fluctuations in community structure of functional networks. These results implicate that ongoing time-resolved resting-state networks, even at short timescales, can to some extent be understood in terms of activation and deactivation of structural eigenmodes and that these eigenmodes play a role in the dynamic integration and segregation of information across the cortex, subserving cognitive functions.

@en

Researchers from various scientific disciplines have attempted to forecast the spread of coronavirus disease 2019 (COVID-19). The proposed epidemic prediction methods range from basic curve fitting methods and traffic interaction models to machine-learning approaches. If we combine all these approaches, we obtain the Network Inference-based Prediction Algorithm (NIPA). In this paper, we analyse a diverse set of COVID-19 forecast algorithms, including several modifications of NIPA. Among the algorithms that we evaluated, the original NIPA performed best at forecasting the spread of COVID-19 in Hubei, China and in the Netherlands. In particular, we show that network-based forecasting is superior to any other forecasting algorithm.

@en

Large-scale neurophysiological networks are often reconstructed from band-pass filtered time series derived from magnetoencephalography (MEG) data. Common practice is to reconstruct these networks separately for different frequency bands and to treat them independently. Recent evidence suggests that this separation may be inadequate, as there can be significant coupling between frequency bands (interlayer connectivity). A multilayer network approach offers a solution to analyze frequency-specific networks in one framework. We propose to use a recently developed network reconstruction method in conjunction with phase oscillator models to estimate interlayer connectivity that optimally fits the empirical data. This approach determines interlayer connectivity based on observed frequency-specific time series of the phase and a connectome derived from diffusion weighted imaging. The performance of this interlayer reconstruction method was evaluated in-silico. Our reconstruction of the underlying interlayer connectivity agreed to very high degree with the ground truth. Subsequently, we applied our method to empirical resting-state MEG data obtained from healthy subjects and reconstructed two-layered networks consisting of either alpha-to-beta or theta-to-gamma band connectivity. Our analysis revealed that interlayer connectivity is dominated by a multiplex structure, i.e. by one-to-one interactions for both alpha-to-beta band and theta-to-gamma band networks. For theta-gamma band networks, we also found a plenitude of interlayer connections between distant nodes, though weaker connectivity relative to the one-to-one connections. Our work is an stepping stone towards the identification of interdependencies across frequency-specific networks. Our results lay the ground for the use of the promising multilayer framework in this field with more-informed and justified interlayer connections.

@en

Infectious diseases typically spread over a contact network with millions of individuals, whose sheer size is a tremendous challenge to analyzing and controlling an epidemic outbreak. For some contact networks, it is possible to group individuals into clusters. A high-level description of the epidemic between a few clusters is considerably simpler than on an individual level. However, to cluster individuals, most studies rely on equitable partitions, a rather restrictive structural property of the contact network. In this work, we focus on Susceptible-Infected-Susceptible (SIS) epidemics, and our contribution is threefold. First, we propose a geometric approach to specify all networks for which an epidemic outbreak simplifies to the interaction of only a few clusters. Second, for the complete graph and any initial viral state vectors, we derive the closed-form solution of the nonlinear differential equations of the N-intertwined mean-field approximation of the SIS process. Third, by relaxing the notion of equitable partitions, we derive low-complexity approximations and bounds for epidemics on arbitrary contact networks. Our results are an important step toward understanding and controlling epidemics on large networks.

@en

The field of epidemiology encompasses a broad class of spreading phenomena, ranging from the seasonal influenza and the dissemination of fake news on online social media to the spread of neural activity over a synaptic network. The propagation of viruses, fake news and neural activity relies on the contact between individuals, social media accounts and brain regions, respectively. The contact patterns of the whole population result in a network. Due to the complexity of such contact networks, the understanding of epidemics is still unsatisfactory. In this dissertation, we advance the theory of epidemics and its applications, with a particular emphasis on the impact of the contact network. Our first contribution focusses on the analysis of the N-Intertwined Mean-Field Approximation (NIMFA) of the Susceptible-Infected-Susceptible (SIS) epidemic process on networks. We propose a geometric approach to clustering for epidemics on networks, which reduces the number of NIMFA differential equations from the network size N to the number m << N of clusters (Chapter 2). Specifically, we show that exact clustering is possible if and only if the contact network has an equitable partition, and we propose an approximate clustering method for arbitrary networks. Furthermore, for arbitrary contact networks, we derive the closed-form solution of the nonlinear NIMFA differential equations around the epidemic threshold (Chapter 3). Our solution reveals that the topology of the contact network is practically irrelevant for the epidemic outbreak around the epidemic threshold. Lastly, we study a discrete-time version of the NIMFA epidemic model (Chapter 4). We derive that the viral state is (almost always) monotonically increasing, the steady state is exponentially stable, and the viral dynamics is bounded by linear time-invariant systems. In the second part, we consider the reconstruction of the contact network and the prediction of epidemic outbreaks. We show that, for the stochastic SIS epidemic process on an individual level, the exact reconstruction of the contact network is impractical. Specifically, the maximum-likelihood SIS network reconstruction is NP-hard, and an accurate reconstruction requires a tremendous number of observations of the epidemic outbreak (Chapter 5). For epidemic models between groups of individuals, we argue that, in the presence of model errors, accurate long-term predictions of epidemic outbreaks are not possible, due to a severely ill-conditioned problem (Chapter 6). Nonetheless, short-term forecasts of epidemics are valuable, and we propose a prediction method which is applicable to a plethora of epidemic models on networks (Chapter 7). As an intermediate step, our prediction method infers the contact network from observations of the epidemic outbreak. Our key result is paradoxical: even though an accurate network reconstruction is impossible, the epidemic outbreak can be predicted accurately. Lastly, we apply our network-inference-based prediction method to the outbreak of COVID-19 (Chapter 8). The third part focusses on spreading phenomena in the human brain. We study the relation between two prominent methods for relating structure and function in the brain: the eigenmode approach and the series expansion approach (Chapter 9). More specifically, we derive closed-form expressions for the optimal coefficients of both approaches, and we demonstrate that the eigenmode approach is preferable to the series expansion approach. Furthermore, we study cross-frequency coupling in magnetoencephalography (MEG) brain networks (Chapter 10). By employing a multilayer network reconstruction method, we show that there are strong one-to-one interactions between the alpha and beta band, and the theta and gamma band. Furthermore, our results show that there are many cross-frequency connections between distant brain regions for theta-gamma coupling.@en

Initially emerged in the Chinese city Wuhan and subsequently spread almost worldwide causing a pandemic, the SARS-CoV-2 virus follows reasonably well the Susceptible–Infectious–Recovered (SIR) epidemic model on contact networks in the Chinese case. In this paper, we investigate the prediction accuracy of the SIR model on networks also for Italy. Specifically, the Italian regions are a metapopulation represented by network nodes and the network links are the interactions between those regions. Then, we modify the network-based SIR model in order to take into account the different lockdown measures adopted by the Italian Government in the various phases of the spreading of the COVID-19. Our results indicate that the network-based model better predicts the daily cumulative infected individuals when time-varying lockdown protocols are incorporated in the classical SIR model.

@en

Functional brain networks are shaped and constrained by the underlying structural network. However, functional networks are not merely a one-to-one reflection of the structural network. Several theories have been put forward to understand the relationship between structural and functional networks. However, it remains unclear how these theories can be unified. Two existing recent theories state that 1) functional networks can be explained by all possible walks in the structural network, which we will refer to as the series expansion approach, and 2) functional networks can be explained by a weighted combination of the eigenmodes of the structural network, the so-called eigenmode approach. To elucidate the unique or common explanatory power of these approaches to estimate functional networks from the structural network, we analysed the relationship between these two existing views. Using linear algebra, we first show that the eigenmode approach can be written in terms of the series expansion approach, i.e., walks on the structural network associated with different hop counts correspond to different weightings of the eigenvectors of this network. Second, we provide explicit expressions for the coefficients for both the eigenmode and series expansion approach. These theoretical results were verified by empirical data from Diffusion Tensor Imaging (DTI) and functional Magnetic Resonance Imaging (fMRI), demonstrating a strong correlation between the mappings based on both approaches. Third, we analytically and empirically demonstrate that the fit of the eigenmode approach to measured functional data is always at least as good as the fit of the series expansion approach, and that errors in the structural data lead to large errors of the estimated coefficients for the series expansion approach. Therefore, we argue that the eigenmode approach should be preferred over the series expansion approach. Results hold for eigenmodes of the weighted adjacency matrices as well as eigenmodes of the graph Laplacian. ​Taken together, these results provide an important step towards unification of existing theories regarding the structure-function relationships in brain networks.

@en

The majority of epidemic models are described by non-linear differential equations which do not have a closed-form solution. Due to the absence of a closed-form solution, the understanding of the precise dynamics of a virus is rather limited. We solve the differential equations of the N-intertwined mean-field approximation of the susceptible-infected-susceptible epidemic process with heterogeneous spreading parameters around the epidemic threshold for an arbitrary contact network, provided that the initial viral state vector is small or parallel to the steady-state vector. Numerical simulations demonstrate that the solution around the epidemic threshold is accurate, also above the epidemic threshold and for general initial viral states that are below the steady-state.

@en

At the moment of writing, the future evolution of the COVID-19 epidemic is unclear. Predictions of the further course of the epidemic are decisive to deploy targeted disease control measures. We consider a network-based model to describe the COVID-19 epidemic in the Hubei province. The network is composed of the cities in Hubei and their interactions (e.g., traffic flow). However, the precise interactions between cities is unknown and must be inferred from observing the epidemic. We propose the Network-Inference-Based Prediction Algorithm (NIPA) to forecast the future prevalence of the COVID-19 epidemic in every city. Our results indicate that NIPA is beneficial for an accurate forecast of the epidemic outbreak.

@en

The underlying core of most epidemic models is the graph that specifies the contacts between healthy and infected individuals. However, in the majority of applications, the contact network is unknown. To understand and predict an epidemic outbreak nonetheless, network reconstruction methods aim to estimate the contact network from viral state observations. This work considers general compartmental epidemic models (GEMF) in discrete time, which describe the viral spread between groups of individuals. The reconstruction of the network translates into a set of linear equations that is severely ill-conditioned. Counterintuitively, we show that the contact network cannot be reconstructed from one epidemic outbreak with any finite machine precision, although an accurate prediction of the epidemic outbreak is possible.

@en

The majority of research on epidemics relies on models which are formulated in continuous-time. However, processing real-world epidemic data and simulating epidemics is done digitally and the continuous-time epidemic models are usually approximated by discrete-time models. In general, there is no guarantee that properties of continuous-time epidemic models, such as the stability of equilibria, also hold for the respective discrete-time approximation. We analyse the discrete-time NIMFA epidemic model on directed networks with heterogeneous spreading parameters. In particular, we show that the viral state is increasing and does not overshoot the steady-state, the steady-state is exponentially stable, and we provide linear systems that bound the viral state evolution. Thus, the discrete-time NIMFA model succeeds to capture the qualitative behaviour of a viral spread and provides a powerful means to study real-world epidemics.@en

The SIS dynamics of the spread of a virus crucially depend on both the network topology and the spreading parameters. Since neither the topology nor the spreading parameters are known for the majority of applications, they have to be inferred from observations of the viral spread. We propose an inference method for both topology and spreading parameters based on a maximum-a-posteriori estimation approach for the sampled-time Markov chain of an SIS process. The resulting estimation problem, given by a mixed-integer optimisation problem, results in exponential computational time if a brute-force approach is employed. By introducing an efficient and accurate, polynomial-time heuristic, the topology of the network can almost always be exactly reconstructed. Notwithstanding, reconstructing the network with a reasonably high accuracy requires a subexponentially increasing number of observations and an exponentially increasing computation time with respect to the number of nodes N. Such long observation periods are hardly realistic, which justifies the claim in the title.

@en