Learning interpretable collective variables for spreading processes on networks

Collective variables (CVs) are low-dimensional projections of high-dimensional system states. They are used to gain insights into complex emergent dynamical behaviors of processes on networks. The relation between CVs and network measures is not well understood and its derivation typically requires detailed knowledge of both the dynamical system and the network topology. In this Letter, we present a data-driven method for algorithmically learning and understanding CVs for binary-state spreading processes on networks of arbitrary topology. We demonstrate our method using four example networks: the stochastic block model, a ring-shaped graph, a random regular graph, and a scale-free network generated by the Albert-Barabási model. Our results deliver evidence for the existence of low-dimensional CVs even in cases that are not yet understood theoretically.

A Dynamic Network Model of Societal Complexity and Resilience Inspired by Tainter's Theory of Collapse

In recent years, several global events have severely disrupted economies and social structures, undermining confidence in the resilience of modern societies. Examples include the COVID-19 pandemic, which brought unprecedented health challenges and economic disruptions, and the emergence of geopolitical tensions and conflicts that have further strained international relations and economic stability. While empirical evidence on the dynamics and drivers of past societal collapse is mounting, a process-based understanding of these dynamics is still in its infancy. Here, we aim to identify and illustrate the underlying drivers of such societal instability or even collapse. The inspiration for this work is Joseph Tainter's theory of the "collapse of complex societies", which postulates that the complexity of societies increases as they solve problems, leading to diminishing returns on complexity investments and ultimately to collapse. In this work, we abstract this theory into a low-dimensional and stylized model of two classes of networked agents, hereafter referred to as "laborers" and "administrators". We numerically model the dynamics of societal complexity, measured as the fraction of "administrators", which was assumed to affect the productivity of connected energy-producing "laborers". We show that collapse becomes increasingly likely as the complexity of the model society continuously increases in response to external stresses that emulate Tainter's abstract notion of problems that societies must solve. We also provide an analytical approximation of the system's dominant dynamics, which matches well with the numerical experiments, and use it to study the influence on network link density, social mobility and productivity. Our work advances the understanding of social-ecological collapse and illustrates its potentially direct link to an ever-increasing societal complexity in response to external shocks or stresses via a self-reinforcing feedback.

Resilience basins of complex systems: An application to prosumer impacts on power grids

Comparable to the traditional notion of stability in system dynamics, resilience is typically measured in a way that assesses the quality of a system's response, for example, the speed of its recovery. We present a broadly applicable complementary measurement framework that quantifies resilience similarly to basin stability by estimating a resilience basin, which reflects the extent of adverse influences that the system can recover from in a sufficient manner. In contrast to basin stability, the adverse influences considered here are not necessarily displacements in state space, but arbitrarily complex impacts to the system, quantified by adequate parameters. As a proof of concept, we present two applications: (i) the well-studied single-node power system as an easy-to-follow example and (ii) a stochastic model of a low-voltage DC power grid undergoing an unregulated energy transition consisting in the random appearance of prosumers. These act as decentral suppliers of photovoltaic power and alter the flow patterns while the grid topology remains unchanged. The resilience measurement framework is applied to evaluate the effect and efficiency of two response options: (i) upgrading the capacity of existing power lines and (ii) installing batteries in the prosumer households. The framework demonstrates that line upgrades can provide potentially unlimited resilience against energy decentralization, while household batteries are inherently limited (achieving ≤70% of the resilience of line upgrades). Further, the framework aids in optimizing budget efficiency by pointing toward threshold budget values as well as budget-dependent ideal strategies for the allocation of line upgrades and for the battery charging algorithm.

Optimizing testing strategies for early detection of disease outbreaks in animal trade networks via MCMC

The animal trades between farms and other livestock holdings form a complex livestock trade network. The movement of animals between trade actors plays an important role in the spread of infectious diseases among premises. Particularly, the outbreak of silent diseases that have no clinically obvious symptoms in the animal trade system should be diagnosed by taking special tests. In practice, the authorities regularly conduct examinations on a random number of farms to make sure that there was no outbreak in the system. However, these actions, which aim to discover and block a disease cascade, are yet far from the effective and optimum solution and often fail to prevent epidemics. A testing strategy is defined as making decisions about distributing the fixed testing budget N between farms/nodes in the network. In this paper, first, we apply different heuristics for selecting sentinel farms on real and synthetic pig-trade networks and evaluate them by simulating disease spreading via the SI epidemic model. Later, we propose a Markov chain Monte Carlo (MCMC) based testing strategy with the aim of early detection of outbreaks. The experimental results show that the proposed method can reasonably well decrease the size of the outbreak on both the realistic synthetic and real trade data. A targeted selection of an N/52 fraction of nodes in the real pig-trade network based on the MCMC or simulated annealing can improve the performance of a baseline strategy by 89%. The best heuristic-based testing strategy results in a 75% reduction in the average size of the outbreak compared to that of the baseline testing strategy.

A Temporal Network Model for Livestock Trade Systems

The movements of animals between farms and other livestock holdings for trading activities form a complex livestock trade network. These movements play an important role in the spread of infectious diseases among premises. For studying the disease spreading among animal holdings, it is of great importance to understand the structure and dynamics of the trade system. In this paper, we propose a temporal network model for animal trade systems. Furthermore, a novel measure of node centrality important for disease spreading is introduced. The experimental results show that the model can reasonably well describe these spreading-related properties of the network and it can generate crucial data for research in the field of the livestock trade system.

Dose-response functions and surrogate models for exploring social contagion in the Copenhagen Networks Study

Spreading dynamics and complex contagion processes on networks are important mechanisms underlying the emergence of critical transitions, tipping points and other non-linear phenomena in complex human and natural systems. Increasing amounts of temporal network data are now becoming available to study such spreading processes of behaviours, opinions, ideas, diseases and innovations to test hypotheses regarding their specific properties. To this end, we here present a methodology based on dose-response functions and hypothesis testing using surrogate data models that randomise most aspects of the empirical data while conserving certain structures relevant to contagion, group or homophily dynamics. We demonstrate this methodology for synthetic temporal network data of spreading processes generated by the adaptive voter model. Furthermore, we apply it to empirical temporal network data from the Copenhagen Networks Study. This data set provides a physically-close-contact network between several hundreds of university students participating in the study over the course of 3 months. We study the potential spreading dynamics of the health-related behaviour "regularly going to the fitness studio" on this network. Based on a hierarchy of surrogate data models, we find that our method neither provides significant evidence for an influence of a dose-response-type network spreading process in this data set, nor significant evidence for homophily. The empirical dynamics in exercise behaviour are likely better described by individual features such as the disposition towards the behaviour, and the persistence to maintain it, as well as external influences affecting the whole group, and the non-trivial network structure. The proposed methodology is generic and promising also for applications to other temporal network data sets and traits of interest.

Moving the epidemic tipping point through topologically targeted social distancing

The epidemic threshold of a social system is the ratio of infection and recovery rate above which a disease spreading in it becomes an epidemic. In the absence of pharmaceutical interventions (i.e. vaccines), the only way to control a given disease is to move this threshold by non-pharmaceutical interventions like social distancing, past the epidemic threshold corresponding to the disease, thereby tipping the system from epidemic into a non-epidemic regime. Modeling the disease as a spreading process on a social graph, social distancing can be modeled by removing some of the graphs links. It has been conjectured that the largest eigenvalue of the adjacency matrix of the resulting graph corresponds to the systems epidemic threshold. Here we use a Markov chain Monte Carlo (MCMC) method to study those link removals that do well at reducing the largest eigenvalue of the adjacency matrix. The MCMC method generates samples from the relative canonical network ensemble with a defined expectation value of λ max . We call this the "well-controlling network ensemble" (WCNE) and compare its structure to randomly thinned networks with the same link density. We observe that networks in the WCNE tend to be more homogeneous in the degree distribution and use this insight to define two ad-hoc removal strategies, which also substantially reduce the largest eigenvalue. A targeted removal of 80% of links can be as effective as a random removal of 90%, leaving individuals with twice as many contacts. Finally, by simulating epidemic spreading via either an SIS or an SIR model on network ensembles created with different link removal strategies (random, WCNE, or degree-homogenizing), we show that tipping from an epidemic to a non-epidemic state happens at a larger critical ratio between infection rate and recovery rate for WCNE and degree-homogenized networks than for those obtained by random removals.

Macroscopic approximation methods for the analysis of adaptive networked agent-based models: Example of a two-sector investment model

In this paper, we propose a statistical aggregation method for agent-based models with heterogeneous agents that interact both locally on a complex adaptive network and globally on a market. The method combines three approaches from statistical physics: (a) moment closure, (b) pair approximation of adaptive network processes, and (c) thermodynamic limit of the resulting stochastic process. As an example of use, we develop a stochastic agent-based model with heterogeneous households that invest in either a fossil-fuel- or renewables-based sector while allocating labor on a competitive market. Using the adaptive voter model, the model describes agents as social learners that interact on a dynamic network. We apply the approximation methods to derive a set of ordinary differential equations that approximate the macrodynamics of the model. A comparison of the reduced analytical model with numerical simulations shows that the approximation fits well for a wide range of parameters. The method makes it possible to use analytical tools to better understand the dynamical properties of models with heterogeneous agents on adaptive networks. We showcase this with a bifurcation analysis that identifies parameter ranges with multistabilities. The method can thus help to explain emergent phenomena from network interactions and make them mathematically traceable.

A network-based microfoundation of Granovetter's threshold model for social tipping

Social tipping, where minorities trigger larger populations to engage in collective action, has been suggested as one key aspect in addressing contemporary global challenges. Here, we refine Granovetter’s widely acknowledged theoretical threshold model of collective behavior as a numerical modelling tool for understanding social tipping processes and resolve issues that so far have hindered such applications. Based on real-world observations and social movement theory, we group the population into certain or potential actors, such that – in contrast to its original formulation – the model predicts non-trivial final shares of acting individuals. Then, we use a network cascade model to explain and analytically derive that previously hypothesized broad threshold distributions emerge if individuals become active via social interaction. Thus, through intuitive parameters and low dimensionality our refined model is adaptable to explain the likelihood of engaging in collective behavior where social-tipping-like processes emerge as saddle-node bifurcations and hysteresis.

Deep reinforcement learning in World-Earth system models to discover sustainable management strategies

Increasingly complex nonlinear World-Earth system models are used for describing the dynamics of the biophysical Earth system and the socioeconomic and sociocultural World of human societies and their interactions. Identifying pathways toward a sustainable future in these models for informing policymakers and the wider public, e.g., pathways leading to robust mitigation of dangerous anthropogenic climate change, is a challenging and widely investigated task in the field of climate research and broader Earth system science. This problem is particularly difficult when constraints on avoiding transgressions of planetary boundaries and social foundations need to be taken into account. In this work, we propose to combine recently developed machine learning techniques, namely, deep reinforcement learning (DRL), with classical analysis of trajectories in the World-Earth system. Based on the concept of the agent-environment interface, we develop an agent that is generally able to act and learn in variable manageable environment models of the Earth system. We demonstrate the potential of our framework by applying DRL algorithms to two stylized World-Earth system models. Conceptually, we explore thereby the feasibility of finding novel global governance policies leading into a safe and just operating space constrained by certain planetary and socioeconomic boundaries. The artificially intelligent agent learns that the timing of a specific mix of taxing carbon emissions and subsidies on renewables is of crucial relevance for finding World-Earth system trajectories that are sustainable in the long term.

Impact of network topology on the stability of DC microgrids

We probe the stability of Watts-Strogatz DC microgrids, in which droop-controlled producers and constant power load consumers are homogeneously distributed and obey Kirchhoff's circuit laws. The concept of survivability is employed to evaluate the system's response to Dirac-delta voltage perturbations at single nodes. A fixed point analysis of the power grid model yields that there is only one relevant attractor. Using a set of simulations with random networks, we investigate correlations between survivability and three topological network measures: the share of producers in the network and the degree and the average neighbor degree of the perturbed node. Depending on the imposed voltage and current limits, the stability is optimized for low node degrees or a specific share of producers. Based on our findings, we provide an insight into the local dynamics of the perturbed system and derive explicit guidelines for the design of resilient DC power grids.

Recurrence threshold selection for obtaining robust recurrence characteristics in different embedding dimensions

The appropriate selection of recurrence thresholds is a key problem in applications of recurrence quantification analysis and related methods across disciplines. Here, we discuss the distribution of pairwise distances between state vectors in the studied system's state space reconstructed by means of time-delay embedding as the key characteristic that should guide the corresponding choice for obtaining an adequate resolution of a recurrence plot. Specifically, we present an empirical description of the distance distribution, focusing on characteristic changes of its shape with increasing embedding dimension. Our results suggest that selecting the recurrence threshold according to a fixed percentile of this distribution reduces the dependence of recurrence characteristics on the embedding dimension in comparison with other commonly used threshold selection methods. Numerical investigations on some paradigmatic model systems with time-dependent parameters support these empirical findings.

Abrupt transitions in time series with uncertainties

Identifying abrupt transitions is a key question in various disciplines. Existing transition detection methods, however, do not rigorously account for time series uncertainties, often neglecting them altogether or assuming them to be independent and qualitatively similar. Here, we introduce a novel approach suited to handle uncertainties by representing the time series as a time-ordered sequence of probability density functions. We show how to detect abrupt transitions in such a sequence using the community structure of networks representing probabilities of recurrence. Using our approach, we detect transitions in global stock indices related to well-known periods of politico-economic volatility. We further uncover transitions in the El Niño-Southern Oscillation which coincide with periods of phase locking with the Pacific Decadal Oscillation. Finally, we provide for the first time an 'uncertainty-aware' framework which validates the hypothesis that ice-rafting events in the North Atlantic during the Holocene were synchronous with a weakened Asian summer monsoon.

Survivability of Deterministic Dynamical Systems

The notion of a part of phase space containing desired (or allowed) states of a dynamical system is important in a wide range of complex systems research. It has been called the safe operating space, the viability kernel or the sunny region. In this paper we define the notion of survivability: Given a random initial condition, what is the likelihood that the transient behaviour of a deterministic system does not leave a region of desirable states. We demonstrate the utility of this novel stability measure by considering models from climate science, neuronal networks and power grids. We also show that a semi-analytic lower bound for the survivability of linear systems allows a numerically very efficient survivability analysis in realistic models of power grids. Our numerical and semi-analytic work underlines that the type of stability measured by survivability is not captured by common asymptotic stability measures.

Unified functional network and nonlinear time series analysis for complex systems science: The pyunicorn package

We introduce the pyunicorn (Pythonic unified complex network and recurrence analysis toolbox) open source software package for applying and combining modern methods of data analysis and modeling from complex network theory and nonlinear time series analysis. pyunicorn is a fully object-oriented and easily parallelizable package written in the language Python. It allows for the construction of functional networks such as climate networks in climatology or functional brain networks in neuroscience representing the structure of statistical interrelationships in large data sets of time series and, subsequently, investigating this structure using advanced methods of complex network theory such as measures and models for spatial networks, networks of interacting networks, node-weighted statistics, or network surrogates. Additionally, pyunicorn provides insights into the nonlinear dynamics of complex systems as recorded in uni- and multivariate time series from a non-traditional perspective by means of recurrence quantification analysis, recurrence networks, visibility graphs, and construction of surrogate time series. The range of possible applications of the library is outlined, drawing on several examples mainly from the field of climatology.

Macroscopic description of complex adaptive networks coevolving with dynamic node states

In many real-world complex systems, the time evolution of the network's structure and the dynamic state of its nodes are closely entangled. Here we study opinion formation and imitation on an adaptive complex network which is dependent on the individual dynamic state of each node and vice versa to model the coevolution of renewable resources with the dynamics of harvesting agents on a social network. The adaptive voter model is coupled to a set of identical logistic growth models and we mainly find that, in such systems, the rate of interactions between nodes as well as the adaptive rewiring probability are crucial parameters for controlling the sustainability of the system's equilibrium state. We derive a macroscopic description of the system in terms of ordinary differential equations which provides a general framework to model and quantify the influence of single node dynamics on the macroscopic state of the network. The thus obtained framework is applicable to many fields of study, such as epidemic spreading, opinion formation, or socioecological modeling.

Quantifying causal coupling strength: a lag-specific measure for multivariate time series related to transfer entropy

While it is an important problem to identify the existence of causal associations between two components of a multivariate time series, a topic addressed in Runge, Heitzig, Petoukhov, and Kurths [Phys. Rev. Lett. 108, 258701 (2012)], it is even more important to assess the strength of their association in a meaningful way. In the present article we focus on the problem of defining a meaningful coupling strength using information-theoretic measures and demonstrate the shortcomings of the well-known mutual information and transfer entropy. Instead, we propose a certain time-delayed conditional mutual information, the momentary information transfer (MIT), as a lag-specific measure of association that is general, causal, reflects a well interpretable notion of coupling strength, and is practically computable. Rooted in information theory, MIT is general in that it does not assume a certain model class underlying the process that generates the time series. As discussed in a previous paper [Runge, Heitzig, Petoukhov, and Kurths, Phys. Rev. Lett. 108, 258701 (2012)], the general framework of graphical models makes MIT causal in that it gives a nonzero value only to lagged components that are not independent conditional on the remaining process. Further, graphical models admit a low-dimensional formulation of conditions, which is important for a reliable estimation of conditional mutual information and, thus, makes MIT practically computable. MIT is based on the fundamental concept of source entropy, which we utilize to yield a notion of coupling strength that is, compared to mutual information and transfer entropy, well interpretable in that, for many cases, it solely depends on the interaction of the two components at a certain lag. In particular, MIT is, thus, in many cases able to exclude the misleading influence of autodependency within a process in an information-theoretic way. We formalize and prove this idea analytically and numerically for a general class of nonlinear stochastic processes and illustrate the potential of MIT on climatological data.

Escaping the curse of dimensionality in estimating multivariate transfer entropy

Multivariate transfer entropy (TE) is a model-free approach to detect causalities in multivariate time series. It is able to distinguish direct from indirect causality and common drivers without assuming any underlying model. But despite these advantages it has mostly been applied in a bivariate setting as it is hard to estimate reliably in high dimensions since its definition involves infinite vectors. To overcome this limitation, we propose to embed TE into the framework of graphical models and present a formula that decomposes TE into a sum of finite-dimensional contributions that we call decomposed transfer entropy. Graphical models further provide a richer picture because they also yield the causal coupling delays. To estimate the graphical model we suggest an iterative algorithm, a modified version of the PC-algorithm with a very low estimation dimension. We present an appropriate significance test and demonstrate the method's performance using examples of nonlinear stochastic delay-differential equations and observational climate data (sea level pressure).

Analytical framework for recurrence network analysis of time series

Recurrence networks are a powerful nonlinear tool for time series analysis of complex dynamical systems. While there are already many successful applications ranging from medicine to paleoclimatology, a solid theoretical foundation of the method has still been missing so far. Here, we interpret an ɛ-recurrence network as a discrete subnetwork of a "continuous" graph with uncountably many vertices and edges corresponding to the system's attractor. This step allows us to show that various statistical measures commonly used in complex network analysis can be seen as discrete estimators of newly defined continuous measures of certain complex geometric properties of the attractor on the scale given by ɛ. In particular, we introduce local measures such as the ɛ-clustering coefficient, mesoscopic measures such as ɛ-motif density, path-based measures such as ɛ-betweennesses, and global measures such as ɛ-efficiency. This new analytical basis for the so far heuristically motivated network measures also provides an objective criterion for the choice of ɛ via a percolation threshold, and it shows that estimation can be improved by so-called node splitting invariant versions of the measures. We finally illustrate the framework for a number of archetypical chaotic attractors such as those of the Bernoulli and logistic maps, periodic and two-dimensional quasiperiodic motions, and for hyperballs and hypercubes by deriving analytical expressions for the novel measures and comparing them with data from numerical experiments. More generally, the theoretical framework put forward in this work describes random geometric graphs and other networks with spatial constraints, which appear frequently in disciplines ranging from biology to climate science.