Data based identification and prediction of nonlinear and complex dynamical systems


Abstract

The problem of reconstructing nonlinear and complex dynamical systems from measured data or time series is central to many scientific disciplines including physical, biological, computer, and social sciences, as well as engineering and economics. The classic approach to phase-space reconstruction through the methodology of delay-coordinate embedding has been practiced for more than three decades, but the paradigm is effective mostly for low-dimensional dynamical systems. Often, the methodology yields only a topological correspondence of the original system. There are situations in various fields of science and engineering where the systems of interest are complex and high dimensional with many interacting components. A complex system typically exhibits a rich variety of collective dynamics, and it is of great interest to be able to detect, classify, understand, predict, and control the dynamics using data that are becoming increasingly accessible due to the advances of modern information technology. To accomplish these tasks, especially prediction and control, an accurate reconstruction of the original system is required.

Nonlinear and complex systems identification aims at inferring, from data, the mathematical equations that govern the dynamical evolution and the complex interaction patterns, or topology, among the various components of the system. With successful reconstruction of the system equations and the connecting topology, it may be possible to address challenging and significant problems such as identification of causal relations among the interacting components and detection of hidden nodes. The “inverse” problem thus presents a grand challenge, requiring new paradigms beyond the traditional delay-coordinate embedding methodology.

The past fifteen years have witnessed rapid development of contemporary complex graph theory with broad applications in interdisciplinary science and engineering. The combination of graph, information, and nonlinear dynamical systems theories with tools from statistical physics, optimization, engineering control, applied mathematics, and scientific computing enables the development of a number of paradigms to address the problem of nonlinear and complex systems reconstruction. In this Review, we review the recent advances in this forefront and rapidly evolving field, with a focus on compressive sensing based methods. In particular, compressive sensing is a paradigm developed in recent years in applied mathematics, electrical engineering, and nonlinear physics to reconstruct sparse signals using only limited data. It has broad applications ranging from image compression/reconstruction to the analysis of large-scale sensor networks, and it has become a powerful technique to obtain high-fidelity signals for applications where sufficient observations are not available. We will describe in detail how compressive sensing can be exploited to address a diverse array of problems in data based reconstruction of nonlinear and complex networked systems. The problems include identification of chaotic systems and prediction of catastrophic bifurcations, forecasting future attractors of time-varying nonlinear systems, reconstruction of complex networks with oscillatory and evolutionary game dynamics, detection of hidden nodes, identification of chaotic elements in neuronal networks, and reconstruction of complex geospatial networks and nodal positioning. A number of alternative methods, such as those based on system response to external driving, synchronization, noise-induced dynamical correlation, will also be discussed. Due to the high relevance of network reconstruction to biological sciences, a special Section is devoted to a brief survey of the current methods to infer biological networks. Finally, a number of open problems including control and controllability of complex nonlinear dynamical networks are discussed.

The methods reviewed in this Review are principled on various concepts in complexity science and engineering such as phase transitions, bifurcations, stabilities, and robustness. The methodologies have the potential to significantly improve our ability to understand a variety of complex dynamical systems ranging from gene regulatory systems to social networks towards the ultimate goal of controlling such systems.


1. Introduction

An outstanding problem in interdisciplinary science is nonlinear and complex systems identification, prediction, and control. Given a complex dynamical system, the various types of dynamical processes are of great interest. The ultimate goal in the study of complex systems is to devise practically implementable strategies to control the collective dynamics. A great challenge is that the network structure and the nodal dynamics are often unknown but only limited measured time series are available. To control the system dynamics, it is imperative to map out the system details from data. Reconstructing complex network structure and dynamics from data, the inverse problem, has thus become a central issue in contemporary network science and engineering  [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31], [32], [33], [34], [35], [36], [37] and [38]. There are broad applications of the solutions of the network reconstruction problem, due to the ubiquity of complex interacting patterns arising from many systems in a variety of disciplines  [39], [40], [41] and [42].

1.1. Existing works on data based reconstruction of nonlinear dynamical systems

The traditional paradigm of nonlinear time series analysis is the delay-coordinate embedding method, the mathematical foundation of which was laid by Takens more than three decades ago  [43]. He proved that, under fairly general conditions, the underlying dynamical system can be faithfully reconstructed from time series in the sense that a one-to-one correspondence can be established between the reconstructed and the true but unknown dynamical systems. Based on the reconstruction, quantities of importance for understanding the system can be estimated, such as the relative weights of deterministicity and stochasticity of the underlying system, its dimensionality, the Lyapunov exponents, and unstable periodic orbits that constitute the skeleton of the invariant set responsible for the observed dynamics.

There exists a large body of literature on the application of the delay-coordinate embedding technique to nonlinear/chaotic dynamical systems  [44] and [45]. A pioneering work in this field is Ref.  [46]. The problem of determining the proper time delay was investigated  [47], [48], [49], [50], [51], [52], [53] and [54], with a firm theoretical foundation established by exploiting the statistics for testing continuity and differentiability from chaotic time series  [55], [56], [57], [58] and [59]. The mathematical foundation for the required embedding dimension for chaotic attractors was laid in Ref.  [60]. There were works on the analysis of transient chaotic time series  [61], [62], [63], [64] and [65], on the reconstruction of dynamical systems with time delay  [66], on detecting unstable periodic orbits from time series  [67], [68], [69], [70], [71] and [72], on computing the fractal dimensions from chaotic data  [73], [74], [75], [76], [77], [78], [53] and [54], and on estimating the Lyapunov exponents  [79], [80], [81], [82], [83], [84] and [85].

There were also works on forecasting nonlinear dynamical systems  [86], [87], [88], [89], [90], [91], [92], [93], [94], [95], [96], [97], [98], [99], [100], [101], [102], [103], [104], [105], [106], [107], [108] and [23]. A conventional approach is to approximate a nonlinear system with a large collection of linear equations in different regions of the phase space to reconstruct the Jacobian matrices on a proper grid [101], [102] and [104] or fit ordinary differential equations to chaotic data  [103]. Approaches based on chaotic synchronization  [106] or genetic algorithms  [107] and [108] to parameter estimation were also investigated. In most existing works, short-term predictions of a dynamical system can be achieved by employing the classical delay-coordinate embedding paradigm  [43] and [44]. For nonstationary systems, the method of over-embedding was introduced  [109] in which the time-varying parameters were treated as independent dynamical variables so that the essential aspects of determinism of the underlying system can be restored. A recently developed framework based on compressive sensing was able to predict the exact forms of both system equations and parameter functions based on available time series for stationary  [23] and time-varying dynamical systems  [25].

1.2. Existing works on data based reconstruction of complex networks and dynamical processes

Data based reconstruction of complex networks in general is deemed to be an important but difficult problem and has attracted continuous interest, where the goal is to uncover the full topology of the network based on simultaneously measured time series  [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31], [32], [33], [34], [35], [36], [37] and [38]. There were previous efforts in nonlinear systems identification and parameter estimation for coupled oscillators and spatiotemporal systems, such as the auto-synchronization method  [106]. There were also works on revealing the connection patterns of networks. For example, methods were proposed to estimate the network topology controlled by feedback or delayed feedback  [6], [9] and [21]. Network connectivity can be reconstructed from the collective dynamical trajectories using response dynamics  [20]. The approach of random phase resetting was introduced to reconstruct the details of the network structure  [18]. For neuronal systems, there was a statistical method to track the structural changes  [28] and [32]. Some earlier methods required more information about the network than just data. For example, the following two approaches require complete information about the dynamical processes, e.g., equations governing the evolutions of all nodes on the network. (1) In Ref.  [6], the detailed dynamics at each node is assumed to be known. A replica of the network, or a computational model of this “target” network, can then be constructed, with the exception that the interaction strengths among the nodes are chosen randomly. It has been demonstrated that in situations where a Lyapunov function for the network dynamics exists, the connectivity of the model network converges to that of the target network  [6]. (2) In Ref.  [8], a Kuramoto-type of phase dynamics  [110] and [111] on the network is assumed, where a steady-state solution exists. By linearizing the network dynamics about the steady-state solution, the associated Jacobian matrix can be obtained, which reflects the network topology and connectivity. Besides requiring complete information about the nodal dynamics, the amount of computations required tends to increase dramatically with the size of the network  [6]. For example, suppose the nodal dynamics is described by a set of differential equations. For a network of size N, in order for its structure to be predicted, the number of differential equations to be solved typically increases with N as N2.

For nonlinear dynamical networks, there was a method  [10] based on chaotic time-series analysis through estimating the elements of the Jacobian matrix, which are the mutual partial derivatives of the dynamical variables on different nodes in the network. A statistically significant entry in the matrix implies a connection between the two nodes specified by the row and the column indices of that entry. Because of the mathematical nature of the Jacobian matrix, i.e., it is meaningful only for infinitesimal tangent vectors, linearization of the dynamics in the neighborhoods of the reconstructed phase-space points is needed, for which constrained optimization techniques  [112], [113], [114], [115], [116], [117] and [118] were found to be effective  [10]. Estimating the Jacobian matrices, however, has been a challenging problem in nonlinear dynamics  [81] and [105] and its reliability can be ensured but only for low-dimensional, deterministic dynamical systems. The method  [10] appeared thus to be limited to small networks with sparse connections.

While many of the earlier works required complete or partial information about the intrinsic dynamics of the nodes and their coupling functions, completely data-driven and model-free methods exist. For example, The global climate network was reconstructed using the mutual information method, enabling energy and information flow in the network to be studied  [14]. The sampling bias of DNA sequences in viruses from different regions can be used to reveal the geospatial topologies of the influenza networks  [16]. Network structure can also be obtained by calculating the causal influences among the time series based on the Granger causality  [119] method  [5], [120], [33], [121] and [122], the overarching framework  [123], the transfer entropy method  [29], or the method of inner composition alignment  [19]. However, such causality based methods are unable to reveal information about the nodal dynamical equations. In addition, there were regression-based methods  [124] for systems identification based on the least squares approximation through the Kronecker-product representation  [125], which would require large amounts of data.

In systems biology, reverse engineering of gene regulatory networks from expression data is a fundamentally important problem, and it attracts a tremendous amount of interest  [126], [127], [128], [129], [130], [131], [132], [133] and [134]. The wide spectrum of methods for modeling genetic regulatory networks can be categorized based on the level of details with which the genetic interactions and dynamics are modeled  [135]. One of the classical mathematical formalisms used to model the dynamics of biological processes is differential equations, which can capture the dynamics of each component in a system at a detailed level  [136], [137] and [138]. A major limitation of this approach is its overwhelming complexity and the resulting computational requirement, which limits its applicability to small-scale systems. In contrast, Boolean network models assume that the states of components in the system are binary and the state transitions are governed by logic operations  [139], [140] and [141]. Since the gene expressions are usually described by their expression levels and the interaction patterns between genes may not be logic operations, in some cases the Boolean network models may not be biologically appropriate. Another class of methods explicitly model biological systems as a graph in which the vertices represent basic units in the system and the edges characterize the relationships between the units. The graph itself can be constructed either by directly comparing the measurements for the vertices based on certain metric, such as the Euclidean distance, mutual information, or correlation coefficient  [142], [143] and [130], or by some probabilistic approaches for Bayesian network learning  [144], [145] and [146]. However, inferring regulatory interactions based on Bayesian networks is an intractable problem  [147] and [148]. The linear regression models for learning regulatory networks assume that expression level of a gene can be approximated by a linear combination of the expressions of other genes  [133], [128], [129] and [149], and such models form a middle ground between the models based on differential equations and Boolean logic.

1.3. Compressive sensing based reconstruction of nonlinear and complex dynamical systems

A recent line of research  [22], [23], [24], [30], [31], [35], [36], [37] and [38] exploited compressive sensing  [113], [114], [115], [116], [117] and [118]. The basic principle is that the dynamics of many natural and man-made systems are determined by smooth enough functions that can be approximated by finite series expansions. The task then becomes that of estimating the coefficients in the series representation of the vector field governing the system dynamics. In general, the series can contain high order terms, and the total number of coefficients to be estimated can be quite large. While this is a challenging problem, if most coefficients are zero (or negligible), the vector constituting all the coefficients will be sparse. In addition, a generic feature of complex networks in the real world is that they are sparse  [42]. Thus for realistic nonlinear dynamical networks, the vectors to be reconstructed are typically sparse, and the problem of sparse vector estimation can then be solved by the paradigm of compressive sensing  [113], [114], [116], [117] and [118] that reconstructs a sparse signal from limited observations. Since the observation requirements can be relaxed considerably as compared to those associated with conventional signal reconstruction schemes, compressive sensing has evolved into a powerful technique to reconstruct sparse signal from small amounts of observations that are much less than those required in conventional approaches. Compressive sensing has been introduced to the field of network reconstruction for discrete time and continuous time nodal dynamics  [23] and [24], for evolutionary game dynamics  [22], for detecting hidden nodes  [31] and [36], for predicting and controlling synchronization dynamics  [30], and for reconstructing spreading dynamics based on binary data  [37]. Compressive sensing also finds applications in quantum measurement science, e.g., to exponentially reduce the experimental configurations required for quantum tomography  [150].

1.4. Plan of this review

This Review presents the recent advances in the forefront and rapidly evolving field of nonlinear and complex dynamical systems identification and prediction. Our focus will be on the compressive sensing based approaches. Alternative approaches will also be discussed, which include noised-induced dynamical mapping, perturbations, reverse engineering, synchronization, inner composition alignment, global silencing, Granger causality, and alternative optimization algorithms.

In Section  2, we first introduce the principle of compressive sensing and discuss nonlinear dynamical systems identification and prediction. We next discuss a compressive sensing based approach to predicting catastrophes in nonlinear dynamical systems under the assumption that the system equations are completely unknown and only time series reflecting the evolution of the dynamical variables of the system are available. We then turn to time-varying nonlinear dynamical systems, motivated by the fact that systems with one or a few parameters varying slowly with time are of considerable interest in many areas of science and engineering. In such a system, the attractors in the future can be characteristically different from those at the present. To predict the possible future attractors based on available information at the present is thus a well-defined and meaningful problem, which is challenging especially when the system equations are not known but only time-series measurements are available. We review a compressive-sensing based method for time-varying systems. This framework allows us to reconstruct the system equations and the time dependence of parameters based on limited measurements so that the future attractors of the system can be predicted through computation.

Section  3 focuses on compressive sensing based reconstruction of complex networked systems. The following problems will be discussed in detail.

Reconstruction of coupled oscillator networks. The basic idea is that the mathematical functions determining the dynamical couplings in a physical network can be expressed by power-series expansions. The task is then to estimate all the nonzero coefficients, which can be accomplished by exploiting compressive sensing  [24].

Reconstruction of social networks based on evolutionary-game data via compressive sensing. Evolutionary games are a common type interactions in a variety of complex networked, natural and social systems. Given such a system, uncovering the interacting structure of the underlying network is key to understanding its collective dynamics. We discuss a compressive sensing based method to uncover the network topology using evolutionary-game data. In particular, in a typical game, agents use different strategies in order to gain the maximum payoff. The strategies can be divided into two types: cooperation and defection. It was shown  [22] that, even when the available information about each agent’s strategy and payoff is limited, the compressive-sensing based approach can yield precise knowledge of the node-to-node interaction patterns in a highly efficient manner. In addition to numerical validation of the method with model complex networks, we discuss an actual social experiment in which participants forming a friendship network played a typical game to generate short sequences of strategy and payoff data. The high prediction accuracy achieved and the unique requirement of extremely small data set suggest that the method can be appealing to potential applications to reveal “hidden” networks embedded in various social and economic systems.

Detecting hidden nodes in complex networks from time series. The power of science lies in its ability to infer and predict the existence of objects from which no direct information can be obtained experimentally or observationally. A well known example is to ascertain the existence of black holes of various masses in different parts of the universe from indirect evidence, such as X-ray emissions. In complex networks, the problem of detecting hidden nodes can be stated, as follows. Consider a network whose topology is completely unknown but whose nodes consist of two types: one accessible and another inaccessible from the outside world. The accessible nodes can be observed or monitored, and we assume that time series are available from each node in this group. The inaccessible nodes are shielded from the outside and they are essentially “hidden”. The question is, can we infer, based solely on the available time series from the accessible nodes, the existence and locations of the hidden nodes? Since no data from the hidden nodes are available, nor can they be observed directly, they act as some sort of “black box” from the outside world. Solution of the network hidden node detection problem has potential applications in different fields of significant current interest. For example, to uncover the topology of a terrorist organization and especially, various ring leaders of the network is a critical task in defense. The leaders may be hidden in the sense that no direct information about them can be obtained, yet they may rely on a number of couriers to operate, which are often subject to surveillance. Similar situations arise in epidemiology, where the original carrier of a virus may be hidden, or in a biology network where one wishes to detect the most influential node from which no direct observation can be made. We discuss in detail a compressive sensing based method  [31] and [36] to ascertain hidden nodes in complex networks and to distinguish them from various noise sources.

Identifying chaotic elements in complex neuronal networks. We discuss a completely data-driven approach  [35] to reconstructing coupled neuronal networks that contain a small subset of chaotic neurons. Such chaotic elements can be the result of parameter shift in their individual dynamical systems, and may lead to abnormal functions of the network. To accurately identify the chaotic neurons may thus be necessary and important, for example, for applying appropriate controls to bring the network to a normal state. However, due to couplings among the nodes the measured time series even from non-chaotic neurons would appear random, rendering inapplicable traditional nonlinear time-series analysis, such as the delay-coordinate embedding method, which yields information about the global dynamics of the entire network. The method to be discussed is based on compressive sensing. In particular, identifying chaotic elements can be formulated as a general problem of reconstructing the nodal dynamical systems, network connections, and all coupling functions as well as their weights.

Data based reconstruction of complex geospatial networks, nodal positioning, and detection of hidden node. Complex geospatial networks with components distributed in the real geophysical space are an important part of the modern infrastructure. Given a complex geospatial network with nodes distributed in a two-dimensional region of the physical space, can the locations of the nodes be determined and their connection patterns be uncovered based solely on data? In realistic applications, time series/signals can be collected from a single location. A key challenge is that the signals collected are necessarily time delayed, due to the varying physical distances from the nodes to the data collection center. We discuss a compressive sensing based approach  [38] that enables reconstruction of the full topology of the underlying geospatial network and more importantly, accurate estimate of the time delays. A standard triangularization algorithm can then be employed to find the physical locations of the nodes in the network. A hidden source or threat, from which no signal can be obtained, can also be detected through accurate detection of all its neighboring nodes. As a geospatial network has the feature that a node tends to connect with geophysically nearby nodes, the localized region that contains the hidden node can be identified.

Reconstructing complex spreading networks with natural diversity and identifying hidden source. Among the various types of collective dynamics on complex networks, propagation or spreading dynamics is of paramount importance as it is directly relevant to issues of tremendous interests such as epidemic and disease outbreak in the human society and virus spreading on computer networks. We discuss a theoretical and computational framework based on compressive sensing to reconstruct networks of arbitrary topologies, in which spreading dynamics with heterogeneous diffusion probabilities take place  [37]. The approach enables identification with high accuracy of the external sources that trigger the spreading dynamics. Especially, a full reconstruction of the stochastic and inhomogeneous interactions presented in the real-world networks can be achieved from small amounts of polarized (binary) data, a virtue of compressive sensing. After the outbreak of diffusion, hidden sources outside the network, from which no direct routes of propagation are available, can be ascertained and located with high confidence. This represents essentially a new paradigm for tracing, monitoring, and controlling epidemic invasion in complex networked systems, which will be of value to defending and preserving the systems against disturbances and attacks.

Section  4 presents a number of alternative methods for reconstructing complex and nonlinear dynamical networks. These are methods based on (1) response of the system to external driving, (2) synchronization (via system clone), (3) phase-space linearization, (4) noise induced dynamical correlation, and (5) automated reverse engineering. In particular, for the system response based method (1), the basic idea was to measure the collective response of the oscillator network to an external driving signal. With repeated measurements of the dynamical states of the nodes under sufficiently independent driving realizations, the network topology can be recovered  [8]. Since complex networks are generally sparse, the number of realizations of external driving can be much smaller than the network size. For the synchronization based method, the idea was to design a replica or a clone system that is sufficiently close to the original network without requiring knowledge about network structure  [6]. From the clone system, the connectivities and interactions among nodes can be obtained directly, realizing network reconstruction. For the phase-space linearization method, L1-minimization in the phase space of a networked system is employed to reconstruct the topology without knowledge of the self-dynamics of nodes and without using any external perturbation to the state of nodes  [10]. For the method based on noise-induced dynamical correlation, the principle was based on exploiting the rich interplay between nonlinear dynamics and stochastic fluctuations  [13], [15] and [27]. Under the condition that the influence of noise on the evolution of infinitesimal tangent vectors in the phase space of the underlying networked dynamical system is dominant, it can be argued  [15] and [27] that the dynamical correlation matrix that can be computed readily from the available nodal time series approximates the network adjacency matrix, fully unveiling the network topology. For the automated reverse engineering method, the approach was based on problem solving using partitioning, automated probing and snipping  [151], a process that is akin to genetic algorithm. Each of the five methods will be described in reasonable details.

Network reconstruction was pioneered in biological sciences. Section  5 is devoted to a concise survey of the approaches to reconstructing biological networks. Those include methods based on correlation, causality, information-theoretic measures, Bayesian inference, regression and resampling, supervision and semi-supervision, transfer and joint entropies, and distinguishing between direct and indirect interactions.

Finally, in Section  6, we offer a general discussion of the field of data-based reconstruction of complex networks and speculate on a number of open problems. These include: localization of diffusion sources in complex networks, reconstruction of complex networks with binary state dynamics, possibility of developing a universal framework of structural estimator and dynamics approximator for complex networks, and a framework of control and controllability for complex nonlinear dynamical networks.

2. Compressive sensing based nonlinear dynamical systems identification

2.1. Introduction to the compressive sensing algorithm

Compressive sensing is a paradigm developed in recent years by applied mathematicians and electrical engineers to reconstruct sparse signals using only limited data  [113], [114], [115], [116], [117] and [118]. The observations are measured by linear projections of the original data on a few predetermined, random vectors. Since the requirement for the observations is considerably less comparing to conventional signal reconstruction schemes, compressive sensing has been deemed as a powerful technique to obtain high-fidelity signal especially in cases where sufficient observations are not available. Compressive sensing has broad applications ranging from image compression/reconstruction to the analysis of large-scale sensor networks  [117] and [118].

Mathematically, the problem of compressive sensing is to reconstruct a vector View the MathML source from linear measurements View the MathML source about View the MathML source in the form:

equation1
where View the MathML source and G is an M×N matrix. By definition, the number of measurements is much less than that of the unknown signal, i.e, M≪N. Accurate recovery of the original signal is possible through the solution of the following convex optimization problem [113] and [114]:
equation2
View the MathML source
where
equation3
View the MathML source
is the l1 norm of vector View the MathML source.

Note to users:
Accepted manuscripts are Articles in Press that have been peer reviewed and accepted for publication by the Editorial Board of this publication. They have not yet been copy edited and/or formatted in the publication house style, and may not yet have the full ScienceDirect functionality, e.g., supplementary files may still need to be added, links to references may not resolve yet etc. The text could still change before final publication.

Although accepted manuscripts do not have all bibliographic details available yet, they can already be cited using the year of online publication and the DOI, as follows: author(s), article title, Publication (year), DOI. Please consult the journal's reference style for the exact appearance of these elements, abbreviation of journal names and use of punctuation.

When the final article is assigned to volumes/issues of the Publication, the Article in Press version will be removed and the final version will appear in the associated published volumes/issues of the Publication. The date the article was first made available online will be carried over.