Predicting network dynamics without requiring the knowledge of the interaction graph.

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.

Recovering Power Grids Using Strategies Based on Network Metrics and Greedy Algorithms.

For this study, we investigated efficient strategies for the recovery of individual links in power grids governed by the direct current (DC) power flow model, under random link failures. Our primary objective was to explore the efficacy of recovering failed links based solely on topological network metrics. In total, we considered 13 recovery strategies, which encompassed 2 strategies based on link centrality values (link betweenness and link flow betweenness), 8 strategies based on the products of node centrality values at link endpoints (degree, eigenvector, weighted eigenvector, closeness, electrical closeness, weighted electrical closeness, zeta vector, and weighted zeta vector), and 2 heuristic strategies (greedy recovery and two-step greedy recovery), in addition to the random recovery strategy. To evaluate the performance of these proposed strategies, we conducted simulations on three distinct power systems: the IEEE 30, IEEE 39, and IEEE 118 systems. Our findings revealed several key insights: Firstly, there were notable variations in the performance of the recovery strategies based on topological network metrics across different power systems. Secondly, all such strategies exhibited inferior performance when compared to the heuristic recovery strategies. Thirdly, the two-step greedy recovery strategy consistently outperformed the others, with the greedy recovery strategy ranking second. Based on our results, we conclude that relying solely on a single metric for the development of a recovery strategy is insufficient when restoring power grids following link failures. By comparison, recovery strategies employing greedy algorithms prove to be more effective choices.

Predicting time-resolved electrophysiological brain networks from structural eigenmodes.

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.

Comparing the accuracy of several network-based COVID-19 prediction algorithms.

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.

Clustering for epidemics on networks: A geometric approach.

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.

Mapping functional brain networks from the structural connectome: Relating the series expansion and eigenmode approaches.

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.

Time-dependent solution of the NIMFA equations around the epidemic threshold.

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.

Comparing multilayer brain networks between groups: Introducing graph metrics and recommendations.

There is an increasing awareness of the advantages of multi-modal neuroimaging. Networks obtained from different modalities are usually treated in isolation, which is however contradictory to accumulating evidence that these networks show non-trivial interdependencies. Even networks obtained from a single modality, such as frequency-band specific functional networks measured from magnetoencephalography (MEG) are often treated independently. Here, we discuss how a multilayer network framework allows for integration of multiple networks into a single network description and how graph metrics can be applied to quantify multilayer network organisation for group comparison. We analyse how well-known biases for single layer networks, such as effects of group differences in link density and/or average connectivity, influence multilayer networks, and we compare four schemes that aim to correct for such biases: the minimum spanning tree (MST), effective graph resistance cost minimisation, efficiency cost optimisation (ECO) and a normalisation scheme based on singular value decomposition (SVD). These schemes can be applied to the layers independently or to the multilayer network as a whole. For correction applied to whole multilayer networks, only the SVD showed sufficient bias correction. For correction applied to individual layers, three schemes (ECO, MST, SVD) could correct for biases. By using generative models as well as empirical MEG and functional magnetic resonance imaging (fMRI) data, we further demonstrated that all schemes were sensitive to identify network topology when the original networks were perturbed. In conclusion, uncorrected multilayer network analysis leads to biases. These biases may differ between centres and studies and could consequently lead to unreproducible results in a similar manner as for single layer networks. We therefore recommend using correction schemes prior to multilayer network analysis for group comparisons.

Integrating cross-frequency and within band functional networks in resting-state MEG: A multi-layer network approach.

Neuronal oscillations exist across a broad frequency spectrum, and are thought to provide a mechanism of interaction between spatially separated brain regions. Since ongoing mental activity necessitates the simultaneous formation of multiple networks, it seems likely that the brain employs interactions within multiple frequency bands, as well as cross-frequency coupling, to support such networks. Here, we propose a multi-layer network framework that elucidates this pan-spectral picture of network interactions. Our network consists of multiple layers (frequency-band specific networks) that influence each other via inter-layer (cross-frequency) coupling. Applying this model to MEG resting-state data and using envelope correlations as connectivity metric, we demonstrate strong dependency between within layer structure and inter-layer coupling, indicating that networks obtained in different frequency bands do not act as independent entities. More specifically, our results suggest that frequency band specific networks are characterised by a common structure seen across all layers, superimposed by layer specific connectivity, and inter-layer coupling is most strongly associated with this common mode. Finally, using a biophysical model, we demonstrate that there are two regimes of multi-layer network behaviour; one in which different layers are independent and a second in which they operate highly dependent. Results suggest that the healthy human brain operates at the transition point between these regimes, allowing for integration and segregation between layers. Overall, our observations show that a complete picture of global brain network connectivity requires integration of connectivity patterns across the full frequency spectrum.

Hierarchical clustering in minimum spanning trees.

The identification of clusters or communities in complex networks is a reappearing problem. The minimum spanning tree (MST), the tree connecting all nodes with minimum total weight, is regarded as an important transport backbone of the original weighted graph. We hypothesize that the clustering of the MST reveals insight in the hierarchical structure of weighted graphs. However, existing theories and algorithms have difficulties to define and identify clusters in trees. Here, we first define clustering in trees and then propose a tree agglomerative hierarchical clustering (TAHC) method for the detection of clusters in MSTs. We then demonstrate that the TAHC method can detect clusters in artificial trees, and also in MSTs of weighted social networks, for which the clusters are in agreement with the previously reported clusters of the original weighted networks. Our results therefore not only indicate that clusters can be found in MSTs, but also that the MSTs contain information about the underlying clusters of the original weighted network.

Reporting delays: A widely neglected impact factor in COVID-19 forecasts.

Epidemic forecasts are only as good as the accuracy of epidemic measurements. Is epidemic data, particularly COVID-19 epidemic data, clean, and devoid of noise? The complexity and variability inherent in data collection and reporting suggest otherwise. While we cannot evaluate the integrity of the COVID-19 epidemic data in a holistic fashion, we can assess the data for the presence of reporting delays. In our work, through the analysis of the first COVID-19 wave, we find substantial reporting delays in the published epidemic data. Motivated by the desire to enhance epidemic forecasts, we develop a statistical framework to detect, uncover, and remove reporting delays in the infectious, recovered, and deceased epidemic time series. Using our framework, we expose and analyze reporting delays in eight regions significantly affected by the first COVID-19 wave. Further, we demonstrate that removing reporting delays from epidemic data by using our statistical framework may decrease the error in epidemic forecasts. While our statistical framework can be used in combination with any epidemic forecast method that intakes infectious, recovered, and deceased data, to make a basic assessment, we employed the classical SIRD epidemic model. Our results indicate that the removal of reporting delays from the epidemic data may decrease the forecast error by up to 50%. We anticipate that our framework will be indispensable in the analysis of novel COVID-19 strains and other existing or novel infectious diseases.

Transition from time-variant to static networks: Timescale separation in N-intertwined mean-field approximation of susceptible-infectious-susceptible epidemics.

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 [under T]̲(r) and T[over ¯](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[over ¯](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[over ¯](r) is almost entirely determined by the basic reproduction number R_{0} of the network. The value of the upper-transition time T[over ¯](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.

Individualized epidemic spreading models predict epilepsy surgery outcomes: A pseudo-prospective study.

Epilepsy surgery is the treatment of choice for drug-resistant epilepsy patients, but up to 50% of patients continue to have seizures one year after the resection. In order to aid presurgical planning and predict postsurgical outcome on a patient-by-patient basis, we developed a framework of individualized computational models that combines epidemic spreading with patient-specific connectivity and epileptogeneity maps: the Epidemic Spreading Seizure and Epilepsy Surgery framework (ESSES). ESSES parameters were fitted in a retrospective study (N = 15) to reproduce invasive electroencephalography (iEEG)-recorded seizures. ESSES reproduced the iEEG-recorded seizures, and significantly better so for patients with good (seizure-free, SF) than bad (nonseizure-free, NSF) outcome. We illustrate here the clinical applicability of ESSES with a pseudo-prospective study (N = 34) with a blind setting (to the resection strategy and surgical outcome) that emulated presurgical conditions. By setting the model parameters in the retrospective study, ESSES could be applied also to patients without iEEG data. ESSES could predict the chances of good outcome after any resection by finding patient-specific model-based optimal resection strategies, which we found to be smaller for SF than NSF patients, suggesting an intrinsic difference in the network organization or presurgical evaluation results of NSF patients. The actual surgical plan overlapped more with the model-based optimal resection, and had a larger effect in decreasing modeled seizure propagation, for SF patients than for NSF patients. Overall, ESSES could correctly predict 75% of NSF and 80.8% of SF cases pseudo-prospectively. Our results show that individualised computational models may inform surgical planning by suggesting alternative resections and providing information on the likelihood of a good outcome after a proposed resection. This is the first time that such a model is validated with a fully independent cohort and without the need for iEEG recordings.

Individualized computational models of epilepsy surgery capture some of the key aspects of seizure propagation and the resective surgery. It is to be established whether this information can be integrated during the presurgical evaluation of the patient to improve surgical planning and the chances of a good surgical outcome. Here we address this question with a pseudo-prospective study that applies a computational framework of seizure propagation and epilepsy surgery­the ESSES framework­in a pseudo-prospective study mimicking the presurgical conditions. We found that within this pseudo-prospective setting, ESSES could correctly predict 75% of NSF and 80.8% of SF cases. This finding suggests the potential of individualised computational models to inform surgical planning by suggesting alternative resections and providing information on the likelihood of a good outcome after a proposed resection.

Topological properties and organizing principles of semantic networks.

Interpreting natural language is an increasingly important task in computer algorithms due to the growing availability of unstructured textual data. Natural Language Processing (NLP) applications rely on semantic networks for structured knowledge representation. The fundamental properties of semantic networks must be taken into account when designing NLP algorithms, yet they remain to be structurally investigated. We study the properties of semantic networks from ConceptNet, defined by 7 semantic relations from 11 different languages. We find that semantic networks have universal basic properties: they are sparse, highly clustered, and many exhibit power-law degree distributions. Our findings show that the majority of the considered networks are scale-free. Some networks exhibit language-specific properties determined by grammatical rules, for example networks from highly inflected languages, such as e.g. Latin, German, French and Spanish, show peaks in the degree distribution that deviate from a power law. We find that depending on the semantic relation type and the language, the link formation in semantic networks is guided by different principles. In some networks the connections are similarity-based, while in others the connections are more complementarity-based. Finally, we demonstrate how knowledge of similarity and complementarity in semantic networks can improve NLP algorithms in missing link inference.

The role of epidemic spreading in seizure dynamics and epilepsy surgery.

Epilepsy surgery is the treatment of choice for drug-resistant epilepsy patients, but only leads to seizure freedom for roughly two in three patients. To address this problem, we designed a patient-specific epilepsy surgery model combining large-scale magnetoencephalography (MEG) brain networks with an epidemic spreading model. This simple model was enough to reproduce the stereo-tactical electroencephalography (SEEG) seizure propagation patterns of all patients (N = 15), when considering the resection areas (RA) as the epidemic seed. Moreover, the goodness of fit of the model predicted surgical outcome. Once adapted for each patient, the model can generate alternative hypothesis of the seizure onset zone and test different resection strategies in silico. Overall, our findings indicate that spreading models based on patient-specific MEG connectivity can be used to predict surgical outcomes, with better fit results and greater reduction on seizure propagation linked to higher likelihood of seizure freedom after surgery. Finally, we introduced a population model that can be individualized by considering only the patient-specific MEG network, and showed that it not only conserves but improves the group classification. Thus, it may pave the way to generalize this framework to patients without SEEG recordings, reduce the risk of overfitting and improve the stability of the analyses.

Moment closure approximations of susceptible-infected-susceptible epidemics on adaptive networks.

The influence of people's individual responses to the spread of contagious phenomena, like the COVID-19 pandemic, is still not well understood. We investigate the Markovian Generalized Adaptive Susceptible-Infected-Susceptible (G-ASIS) epidemic model. The G-ASIS model comprises many contagious phenomena on networks, ranging from epidemics and information diffusion to innovation spread and human brain interactions. The connections between nodes in the G-ASIS model change adaptively over time, because nodes make decisions to create or break links based on the health state of their neighbors. Our contribution is fourfold. First, we rigorously derive the first-order and second-order mean-field approximations from the continuous-time Markov chain. Second, we illustrate that the first-order mean-field approximation fails to approximate the epidemic threshold of the Markovian G-ASIS model accurately. Third, we show that the second-order mean-field approximation is a qualitative good approximation of the Markovian G-ASIS model. Finally, we discuss the Adaptive Information Diffusion (AID) model in detail, which is contained in the G-ASIS model. We show that, similar to most other instances of the G-ASIS model, the AID model possesses a unique steady state, but that in the AID model, the convergence time toward the steady state is very large. Our theoretical results are supported by numerical simulations.

Fréchet distribution in geometric graphs for drone networks.

In this paper, we focus on the link density in random geometric graphs (RGGs) with a distance-based connection function. After deriving the link density in D dimensions, we focus on the two-dimensional (2D) and three-dimensional (3D) space and show that the link density is accurately approximated by the Fréchet distribution, for any rectangular space. We derive expressions, in terms of the link density, for the minimum number of nodes needed in the 2D and 3D spaces to ensure network connectivity. These results provide first-order estimates for, e.g., a swarm of drones to provide coverage in a disaster or crowded area.

Analysis of continuous-time Markovian ɛ-SIS epidemics on networks.

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.

Accuracy of predicting epidemic outbreaks.

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.

Epidemic models characterize seizure propagation and the effects of epilepsy surgery in individualized brain networks based on MEG and invasive EEG recordings.

Epilepsy surgery is the treatment of choice for drug-resistant epilepsy patients. However, seizure-freedom is currently achieved in only 2/3 of the patients after surgery. In this study we have developed an individualized computational model based on MEG brain networks to explore seizure propagation and the efficacy of different virtual resections. Eventually, the goal is to obtain individualized models to optimize resection strategy and outcome. We have modelled seizure propagation as an epidemic process using the susceptible-infected (SI) model on individual brain networks derived from presurgical MEG. We included 10 patients who had received epilepsy surgery and for whom the surgery outcome at least one year after surgery was known. The model parameters were tuned in in order to reproduce the patient-specific seizure propagation patterns as recorded with invasive EEG. We defined a personalized search algorithm that combined structural and dynamical information to find resections that maximally decreased seizure propagation for a given resection size. The optimal resection for each patient was defined as the smallest resection leading to at least a 90% reduction in seizure propagation. The individualized model reproduced the basic aspects of seizure propagation for 9 out of 10 patients when using the resection area as the origin of epidemic spreading, and for 10 out of 10 patients with an alternative definition of the seed region. We found that, for 7 patients, the optimal resection was smaller than the resection area, and for 4 patients we also found that a resection smaller than the resection area could lead to a 100% decrease in propagation. Moreover, for two cases these alternative resections included nodes outside the resection area. Epidemic spreading models fitted with patient specific data can capture the fundamental aspects of clinically observed seizure propagation, and can be used to test virtual resections in silico. Combined with optimization algorithms, smaller or alternative resection strategies, that are individually targeted for each patient, can be determined with the ultimate goal to improve surgery outcome. MEG-based networks can provide a good approximation of structural connectivity for computational models of seizure propagation, and facilitate their clinical use.