Forecasting synchronizability of complex networks from data

General optimization framework for accurate and efficient reconstruction of symmetric complex networks from dynamical data

The challenging problem of network reconstruction from dynamical data can in general be formulated as an optimization task of solving multiple linear equations. Existing approaches are of the two types: Point-by-point (PBP) and global methods. The local PBP method is computationally efficient, but the accuracies of its solutions are somehow low, while a global method has the opposite traits: High accuracy and high computational cost. Taking advantage of the network symmetry, we develop a novel framework integrating the advantages of both the PBP and global methods while avoiding their shortcomings: i.e., high reconstruction accuracy is guaranteed, but the computational cost is orders of magnitude lower than that of the global methods in the literature. The mathematical principle underlying our framework is block coordinate descent (BCD) for solving optimization problems, where the various blocks are determined by the network symmetry. The reconstruction framework is validated by numerical examples with a variety of network structures (i.e., sparse and dense networks) and dynamical processes. Our success is a demonstration that the general principle of exploiting symmetry can be extended to tackling the challenging inverse problem or reverse engineering of complex networks. Since solving a large number of linear equations is key to a plethora of problems in science and engineering, our BCD-based network reconstruction framework will find broader applications.

Identification of disease propagation paths in two-layer networks

To determine the path of disease in different types of networks, a new method based on compressive sensing is proposed for identifying the disease propagation paths in two-layer networks. If a limited amount of data from network nodes is collected, according to the principle of compressive sensing, it is feasible to accurately identify the path of disease propagation in a multilayer network. Experimental results show that the method can be applied to various networks, such as scale-free networks, small-world networks, and random networks. The impact of network density on identification accuracy is explored. The method could be used to aid in the prevention of disease spread.

Finding nonlinear system equations and complex network structures from data: A sparse optimization approach

In applications of nonlinear and complex dynamical systems, a common situation is that the system can be measured, but its structure and the detailed rules of dynamical evolution are unknown. The inverse problem is to determine the system equations and structure from time series. The principle of exploiting sparse optimization to find the equations of dynamical systems from data was first articulated in 2011 by the ASU group. The basic idea is to expand the system equations into a power series or a Fourier series of a finite number of terms and then to determine the vector of the expansion coefficients based solely on data through sparse optimization. This Tutorial presents a brief review of the recent progress in this area. Issues discussed include discovering the equations of stationary or nonstationary chaotic systems to enable the prediction of critical transition and system collapse, inferring the full topology of complex oscillator networks and social networks hosting evolutionary game dynamics, and identifying partial differential equations for spatiotemporal dynamical systems. Situations where sparse optimization works or fails are pointed out. The relation with the traditional delay-coordinate embedding method is discussed, and the recent development of a model-free, data-driven prediction framework based on machine learning is mentioned.

Compressive sensing-based topology identification of multilayer networks

Recovering network topologies is of great significance in the study of complex networks. In this paper, a method for identifying structures of multilayer networks is proposed via compressive sensing and Taylor expansion. By using this method, the topologies of multilayer networks with unknown node dynamical functions can be identified from a relatively small number of observations. Numerical experiments are provided to show the effectiveness and efficiency of the method on different types of multilayer networks, where the intralayer topology and the interlayer topology of a multilayer network can be identified simultaneously. In particular, the topology of one layer can be identified even when nodes of the other layer are unobservable.

Statistical inference approach to structural reconstruction of complex networks from binary time series

Complex networks hosting binary-state dynamics arise in a variety of contexts. In spite of previous works, to fully reconstruct the network structure from observed binary data remains challenging. We articulate a statistical inference based approach to this problem. In particular, exploiting the expectation-maximization (EM) algorithm, we develop a method to ascertain the neighbors of any node in the network based solely on binary data, thereby recovering the full topology of the network. A key ingredient of our method is the maximum-likelihood estimation of the probabilities associated with actual or nonexistent links, and we show that the EM algorithm can distinguish the two kinds of probability values without any ambiguity, insofar as the length of the available binary time series is reasonably long. Our method does not require any a priori knowledge of the detailed dynamical processes, is parameter-free, and is capable of accurate reconstruction even in the presence of noise. We demonstrate the method using combinations of distinct types of binary dynamical processes and network topologies, and provide a physical understanding of the underlying reconstruction mechanism. Our statistical inference based reconstruction method contributes an additional piece to the rapidly expanding "toolbox" of data based reverse engineering of complex networked systems.

Sparse dynamical Boltzmann machine for reconstructing complex networks with binary dynamics

Revealing the structure and dynamics of complex networked systems from observed data is a problem of current interest. Is it possible to develop a completely data-driven framework to decipher the network structure and different types of dynamical processes on complex networks? We develop a model named sparse dynamical Boltzmann machine (SDBM) as a structural estimator for complex networks that host binary dynamical processes. The SDBM attains its topology according to that of the original system and is capable of simulating the original binary dynamical process. We develop a fully automated method based on compressive sensing and a clustering algorithm to construct the SDBM. We demonstrate, for a variety of representative dynamical processes on model and real world complex networks, that the equivalent SDBM can recover the network structure of the original system and simulates its dynamical behavior with high precision.

Reconstructing complex networks without time series

In the real world there are situations where the network dynamics are transient (e.g., various spreading processes) and the final nodal states represent the available data. Can the network topology be reconstructed based on data that are not time series? Assuming that an ensemble of the final nodal states resulting from statistically independent initial triggers (signals) of the spreading dynamics is available, we develop a maximum likelihood estimation-based framework to accurately infer the interaction topology. For dynamical processes that result in a binary final state, the framework enables network reconstruction based solely on the final nodal states. Additional information, such as the first arrival time of each signal at each node, can improve the reconstruction accuracy. For processes with a uniform final state, the first arrival times can be exploited to reconstruct the network. We derive a mathematical theory for our framework and validate its performance and robustness using various combinations of spreading dynamics and real-world network topologies.

Data-based reconstruction of complex geospatial networks, nodal positioning and detection of hidden nodes

Given a complex geospatial network with nodes distributed in a two-dimensional region of physical space, can the locations of the nodes be determined and their connection patterns be uncovered based solely on data? We consider the realistic situation where 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 centre. To meet this challenge, we develop a compressive-sensing-based approach enabling 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. We further demonstrate successful detection of a hidden node (or a hidden source or threat), from which no signal can be obtained, through accurate detection of all its neighbouring 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.

Recovering network topologies via Taylor expansion and compressive sensing

Gaining knowledge of the intrinsic topology of a complex dynamical network is the precondition to understand its evolutionary mechanisms and to control its dynamical and functional behaviors. In this article, a general framework is developed to recover topologies of complex networks with completely unknown node dynamics based on Taylor expansion and compressive sensing. Numerical simulations illustrate the feasibility and effectiveness of the proposed method. Moreover, this method is found to have good robustness to weak stochastic perturbations. Finally, the impact of two major factors on the topology identification performance is evaluated. This method provides a natural and direct point to reconstruct network topologies from measurable data, which is likely to have potential applicability in a wide range of fields.

Information dissipation as an early-warning signal for the Lehman Brothers collapse in financial time series

In financial markets, participants locally optimize their profit which can result in a globally unstable state leading to a catastrophic change. The largest crash in the past decades is the bankruptcy of Lehman Brothers which was followed by a trust-based crisis between banks due to high-risk trading in complex products. We introduce information dissipation length (IDL) as a leading indicator of global instability of dynamical systems based on the transmission of Shannon information, and apply it to the time series of USD and EUR interest rate swaps (IRS). We find in both markets that the IDL steadily increases toward the bankruptcy, then peaks at the time of bankruptcy, and decreases afterwards. Previously introduced indicators such as ‘critical slowing down' do not provide a clear leading indicator. Our results suggest that the IDL may be used as an early-warning signal for critical transitions even in the absence of a predictive model.