Reconstructing weighted networks from dynamics

Detecting hidden nodes in networks based on random variable resetting method

Reconstructing network connections from measurable data facilitates our understanding of the mechanism of interactions between nodes. However, the unmeasurable nodes in real networks, also known as hidden nodes, introduce new challenges for reconstruction. There have been some hidden node detection methods, but most of them are limited by system models, network structures, and other conditions. In this paper, we propose a general theoretical method for detecting hidden nodes based on the random variable resetting method. We construct a new time series containing hidden node information based on the reconstruction results of random variable resetting, theoretically analyze the autocovariance of the time series, and finally provide a quantitative criterion for detecting hidden nodes. We numerically simulate our method in discrete and continuous systems and analyze the influence of main factors. The simulation results validate our theoretical derivation and illustrate the robustness of the detection method under different conditions.

Diverse phase transitions in optimized directed network models with distinct inward and outward node weights

We consider growing directed network models that aim at minimizing the weighted connection expenses while at the same time favoring other important network properties such as weighted local node degrees. We employed statistical mechanics methods to study the growth of directed networks under the principle of optimizing some objective function. By mapping the system to an Ising spin model, analytic results are derived for two such models, exhibiting diverse and interesting phase transition behaviors for general edge weight, inward and outward node weight distributions. In addition, the unexplored cases of negative node weights are also investigated. Analytic results for the phase diagrams are derived showing even richer phase transition behavior, such as first-order transition due to symmetry, second-order transitions with possible reentrance, and hybrid phase transitions. We further extend previously developed zero-temperature simulation algorithm for undirected networks to the present directed case and for negative node weights, and we can obtain the minimal cost connection configuration efficiently. All the theoretical results are explicitly verified by simulations. Possible applications and implications are also discussed.

GAN-based deep learning framework of network reconstruction

Inferring the topology of a network from network dynamics is a significant problem with both theoretical research significance and practical value. This paper considers how to reconstruct the network topology according to the continuous-time data on the network. Inspired by the generative adversarial network(GAN), we design a deep learning framework based on network continuous-time data. The framework predicts the edge connection probability between network nodes by learning the correlation between network node state vectors. To verify the accuracy and adaptability of our method, we conducted extensive experiments on scale-free networks and small-world networks at different network scales using three different dynamics: heat diffusion dynamics, mutualistic interaction dynamics, and gene regulation dynamics. Experimental results show that our method significantly outperforms the other five traditional correlation indices, which demonstrates that our method can reconstruct the topology of different scale networks well under different network dynamics.

Efficient reconstruction of directed networks from noisy dynamics using stochastic force inference

We consider coupled network dynamics under uncorrelated noises that fluctuate about the noise-free long-time asymptotic state. Our goal is to reconstruct the directed network only from the time-series data of the dynamics of the nodes. By using the stochastic force inference method with a simple natural choice of linear polynomial basis, we derive a reconstruction scheme of the connection weights and the noise strength of each node. Explicit simulations for directed and undirected random networks with various node dynamics are carried out to demonstrate the good accuracy and high efficiency of the reconstruction scheme. We further consider the case when only a subset of the network and its node dynamics can be observed, and it is demonstrated that the directed weighted connections among the observed nodes can be easily and faithfully reconstructed. In addition, we propose a scheme to infer the number of hidden nodes and their effects on each observed node. The accuracy of these results is illustrated by simulations.

Network structure from a characterization of interactions in complex systems

Many natural and man-made complex dynamical systems can be represented by networks with vertices representing system units and edges the coupling between vertices. If edges of such a structural network are inaccessible, a widely used approach is to identify them with interactions between vertices, thereby setting up a functional network. However, it is an unsolved issue if and to what extent important properties of a functional network on the global and the local scale match those of the corresponding structural network. We address this issue by deriving functional networks from characterizing interactions in paradigmatic oscillator networks with widely-used time-series-analysis techniques for various factors that alter the collective network dynamics. Surprisingly, we find that particularly key constituents of functional networks—as identified with betweenness and eigenvector centrality—coincide with ground truth to a high degree, while global topological and spectral properties—clustering coefficient, average shortest path length, assortativity, and synchronizability—clearly deviate. We obtain similar concurrences for an empirical network. Our findings are of relevance for various scientific fields and call for conceptual and methodological refinements to further our understanding of the relationship between structure and function of complex dynamical systems.

Reconstructing distant interactions of multiple paths between perceptible nodes in dark networks

Quantitative research of interdisciplinary fields, including biological and social systems, has attracted great attention in recent years. Complex networks are popular and important tools for the investigations. Explosively increasing data are created by practical networks, from which useful information about dynamic networks can be extracted. From data to network structure, i.e., network reconstruction, is a crucial task. There are many difficulties in fulfilling network reconstruction, including data shortage (existence of hidden nodes) and time delay for signal propagation between adjacent nodes. In this paper a deep network reconstruction method is proposed, which can work in the conditions that even only two nodes (say A and B) are perceptible and all other network nodes are hidden. With a well-designed stochastic driving on node A, this method can reconstruct multiple interaction paths from A to B based on measured data. The distance, effective intensity, and transmission time delay of each path can be inferred accurately.

Revealing directed effective connectivity of cortical neuronal networks from measurements

In the study of biological networks, one of the major challenges is to understand the relationships between network structure and dynamics. In this paper, we model in vitro cortical neuronal cultures as stochastic dynamical systems and apply a method that reconstructs directed networks from dynamics [Ching and Tam, Phys. Rev. E 95, 010301(R) (2017)2470-004510.1103/PhysRevE.95.010301] to reveal directed effective connectivity, namely, the directed links and synaptic weights, of the neuronal cultures from voltage measurements recorded by a multielectrode array. The effective connectivity so obtained reproduces several features of cortical regions in rats and monkeys and has similar network properties as the synaptic network of the nematode Caenorhabditis elegans, whose entire nervous system has been mapped out. The distribution of the incoming degree is bimodal and the distributions of the average incoming and outgoing synaptic strength are non-Gaussian with long tails. The effective connectivity captures different information from the commonly studied functional connectivity, estimated using statistical correlation between spiking activities. The average synaptic strengths of excitatory incoming and outgoing links are found to increase with the spiking activity in the estimated effective connectivity but not in the functional connectivity estimated using the same sets of voltage measurements. These results thus demonstrate that the reconstructed effective connectivity can capture the general properties of synaptic connections and better reveal relationships between network structure and dynamics.

Optimized two-dimensional networks with edge-crossing cost: Frustrated antiferromagnetic spin system

We consider a quasi-two-dimensional network connection growth model that minimizes the wiring cost while maximizing the network connections, but at the same time edge crossings are penalized or forbidden. This model is mapped to a dilute antiferromagnetic Ising spin system with frustrations. We obtain analytic results for the order-parameter or mean degree of the optimized network using mean-field theories. The cost landscape is analyzed in detail showing complex structures due to frustration as the crossing penalty increases. For the case of strictly no edge crossing is allowed, the mean-field equations lead to a new algorithm that can effectively find the (near) optimal solution even for this strongly frustrated system. All these results are also verified by Monte Carlo simulations and numerical solution of the mean-field equations. Possible applications and relation to the planar triangulation problem is also discussed.

Effects of hidden nodes on noisy network dynamics

We consider coupled network dynamics under uncorrelated noises, but only a subset of the network and their node dynamics can be observed. The effects of hidden nodes on the dynamics of the observed nodes can be viewed as having an extra effective noise acting on the observed nodes. These effective noises possess spatial and temporal correlations whose properties are related to the hidden connections. The spatial and temporal correlations of these effective noises are analyzed analytically and the results are verified by simulations on undirected and directed weighted random networks and small-world networks. Furthermore, by exploiting the network reconstruction relation for the observed network noisy dynamics, we propose a scheme to infer information of the effects of the hidden nodes such as the total number of hidden nodes and the weighted total hidden connections on each observed node. The accuracy of these results are demonstrated by explicit simulations.

Detecting interactions in discrete-time dynamics by random variable resetting

Detecting the interactions in networks helps us to understand the collective behaviors of complex systems. However, doing so is challenging due to systemic noise, nonlinearity, and a lack of information. Very few researchers have attempted to reconstruct discrete-time dynamic networks. Recently, Shi et al. proposed resetting a random state variable to infer the interactions in a continuous-time dynamic network. In this paper, we introduce a random resetting method for discrete-time dynamic networks. The statistical characteristics of the method are investigated and verified with numerical simulations. In addition, this reconstruction method was evaluated for limited data and weak coupling and within multiple-attractor systems.

Exploring node interaction relationship in complex networks by using high-frequency signal injection

Many practical systems can be described by complex networks. These networks produce, day and night, rich data which can be used to extract information from the systems. Often, output data of some nodes in the networks can be successfully measured and collected while the structures of networks producing these data are unknown. Thus, revealing network structures by analyzing available data, referred to as network reconstruction, turns to be an important task in many realistic problems. Limitation of measurable data is a very common challenge in network reconstruction. Here we consider an extreme case, i.e., we can only measure and process the data of a pair of nodes in a large network, and the task is to explore the relationship between these two nodes while all other nodes in the network are hidden. A driving-response approach is proposed to do so. By loading a high-frequency signal to a node (defined as node A), we can measure data of the partner node (node B), and work out the connection structure, such as the distance from node A to node B and the effective intensity of interaction from A to B, with the data of node B only. A systematical smoothing technique is suggested for treating noise problem. The approach has practical significance.

Deriving pairwise transfer entropy from network structure and motifs

Transfer entropy (TE) is an established method for quantifying directed statistical dependencies in neuroimaging and complex systems datasets. The pairwise (or bivariate) TE from a source to a target node in a network does not depend solely on the local source-target link weight, but on the wider network structure that the link is embedded in. This relationship is studied using a discrete-time linearly coupled Gaussian model, which allows us to derive the TE for each link from the network topology. It is shown analytically that the dependence on the directed link weight is only a first approximation, valid for weak coupling. More generally, the TE increases with the in-degree of the source and decreases with the in-degree of the target, indicating an asymmetry of information transfer between hubs and low-degree nodes. In addition, the TE is directly proportional to weighted motif counts involving common parents or multiple walks from the source to the target, which are more abundant in networks with a high clustering coefficient than in random networks. Our findings also apply to Granger causality, which is equivalent to TE for Gaussian variables. Moreover, similar empirical results on random Boolean networks suggest that the dependence of the TE on the in-degree extends to nonlinear dynamics.

Identifying the pulsed neuron networks' structures by a nonlinear Granger causality method

Background

It is a crucial task of brain science researches to explore functional connective maps of Biological Neural Networks (BNN). The maps help to deeply study the dominant relationship between the structures of the BNNs and their network functions.

Results

In this study, the ideas of linear Granger causality modeling and causality identification are extended to those of nonlinear Granger causality modeling and network structure identification. We employed Radial Basis Functions to fit the nonlinear multivariate dynamical responses of BNNs with neuronal pulse firing. By introducing the contributions from presynaptic neurons and detecting whether the predictions for postsynaptic neurons’ pulse firing signals are improved or not, we can reveal the information flows distribution of BNNs. Thus, the functional connections from presynaptic neurons can be identified from the obtained network information flows. To verify the effectiveness of the proposed method, the Nonlinear Granger Causality Identification Method (NGCIM) is applied to the network structure discovery processes of Spiking Neural Networks (SNN). SNN is a simulation model based on an Integrate-and-Fire mechanism. By network simulations, the multi-channel neuronal pulse sequence data of the SNNs can be used to reversely identify the synaptic connections and strengths of the SNNs.

Conclusions

The identification results show: for 2–6 nodes small-scale neural networks, 20 nodes medium-scale neural networks, and 100 nodes large-scale neural networks, the identification accuracy of NGCIM with the Gaussian kernel function was 100%, 99.64%, 98.64%, 98.37%, 98.31%, 84.87% and 80.56%, respectively. The identification accuracies were significantly higher than those of a traditional Linear Granger Causality Identification Method with the same network sizes. Thus, with an accumulation of the data obtained by the existing measurement methods, such as Electroencephalography, functional Magnetic Resonance Imaging, and Multi-Electrode Array, the NGCIM can be a promising network modeling method to infer the functional connective maps of BNNs.

Model reconstruction from temporal data for coupled oscillator networks

In a complex system, the interactions between individual agents often lead to emergent collective behavior such as spontaneous synchronization, swarming, and pattern formation. Beyond the intrinsic properties of the agents, the topology of the network of interactions can have a dramatic influence over the dynamics. In many studies, researchers start with a specific model for both the intrinsic dynamics of each agent and the interaction network and attempt to learn about the dynamics of the model. Here, we consider the inverse problem: given data from a system, can one learn about the model and the underlying network? We investigate arbitrary networks of coupled phase oscillators that can exhibit both synchronous and asynchronous dynamics. We demonstrate that, given sufficient observational data on the transient evolution of each oscillator, machine learning can reconstruct the interaction network and identify the intrinsic dynamics.

Network Reconstruction and Community Detection from Dynamics

We present a scalable nonparametric Bayesian method to perform network reconstruction from observed functional behavior that at the same time infers the communities present in the network. We show that the joint reconstruction with community detection has a synergistic effect, where the edge correlations used to inform the existence of communities are also inherently used to improve the accuracy of the reconstruction which, in turn, can better inform the uncovering of communities. We illustrate the use of our method with observations arising from epidemic models and the Ising model, both on synthetic and empirical networks, as well as on data containing only functional information.

Reconstructing positive and negative couplings in Ising spin networks by sorted local transfer entropy

We employ the sorted local transfer entropy (SLTE) to reconstruct the coupling strengths of Ising spin networks with positive and negative couplings (J_{ij}), using only the time-series data of the spins. The SLTE method is model-free in the sense that no knowledge of the underlying dynamics of the spin system is required and is applicable to a broad class of systems. Contrary to the inference of coupling from pairwise transfer entropy, our method can reliably distinguish spin pair interactions with positive and negative couplings. The method is tested for the inverse Ising problem for different J_{ij} distributions and various spin dynamics, including synchronous and asynchronous update Glauber dynamics and Kawasaki exchange dynamics. It is found that the pairwise SLTE is proportional to the pairwise coupling strength to a good extent for all cases studied. In addition, the reconstruction works well for both the equilibrium and nonequilibrium cases of the time-series data. Comparison to other inverse Ising problem approaches using mean-field equations is also discussed.

Reconstruction of dynamic networks with time-delayed interactions in the presence of fast-varying noises

Most complex social, biological and technological systems can be described by dynamic networks. Reconstructing network structures from measurable data is a fundamental problem in almost all interdisciplinary fields. Network nodes interact with each other and those interactions often have diversely distributed time delays. Accurate reconstruction of any targeted interaction to a node requires measured data of all its neighboring nodes together with information on the time delays of interactions from these neighbors. When networks are large, these data are often not available and time-delay factors are deeply hidden. Here we show that fast-varying noise can be of great help in solving these challenging problems. By computing suitable correlations, we can infer the intensity and time delay of any targeted interaction with the data of two related nodes (driving and driven nodes) only while all other nodes in the network are hidden. This method is analytically derived and fully justified by extensive numerical simulations.

Inferring directed networks using a rank-based connectivity measure

Inferring the topology of a network using the knowledge of the signals of each of the interacting units is key to understanding real-world systems. One way to address this problem is using data-driven methods like cross-correlation or mutual information. However, these measures lack the ability to distinguish the direction of coupling. Here, we use a rank-based nonlinear interdependence measure originally developed for pairs of signals. This measure not only allows one to measure the strength but also the direction of the coupling. Our results for a system of coupled Lorenz dynamics show that we are able to consistently infer the underlying network for a subrange of the coupling strength and link density. Furthermore, we report that the addition of dynamical noise can benefit the reconstruction. Finally, we show an application to multichannel electroencephalographic recordings from an epilepsy patient.

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.

Reconstruction of noise-driven nonlinear networks from node outputs by using high-order correlations

Many practical systems can be described by dynamic networks, for which modern technique can measure their outputs, and accumulate extremely rich data. Nevertheless, the network structures producing these data are often deeply hidden in the data. The problem of inferring network structures by analyzing the available data, turns to be of great significance. On one hand, networks are often driven by various unknown facts, such as noises. On the other hand, network structures of practical systems are commonly nonlinear, and different nonlinearities can provide rich dynamic features and meaningful functions of realistic networks. Although many works have considered each fact in studying network reconstructions, much less papers have been found to systematically treat both difficulties together. Here we propose to use high-order correlation computations (HOCC) to treat nonlinear dynamics; use two-time correlations to decorrelate effects of network dynamics and noise driving; and use suitable basis and correlator vectors to unifiedly infer all dynamic nonlinearities, topological interaction links and noise statistical structures. All the above theoretical frameworks are constructed in a closed form and numerical simulations fully verify the validity of theoretical predictions.

Reconstructing network topology and coupling strengths in directed networks of discrete-time dynamics

Reconstructing network connection topology and interaction strengths solely from measurement of the dynamics of the nodes is a challenging inverse problem of broad applicability in various areas of science and engineering. For a discrete-time step network under noises whose noise-free dynamics is stationary, we derive general analytic results relating the weighted connection matrix of the network to the correlation functions obtained from time-series measurements of the nodes for networks with one-dimensional intrinsic node dynamics. Information about the intrinsic node dynamics and the noise strengths acting on the nodes can also be obtained. Based on these results, we develop a scheme that can reconstruct the above information of the network using only the time-series measurements of node dynamics as input. Reconstruction formulas for higher-dimensional node dynamics are also derived and illustrated with a two-dimensional node dynamics network system. Furthermore, we extend our results and obtain a reconstruction scheme even for the cases when the noise-free dynamics is periodic. We demonstrate that our method can give accurate reconstruction results for weighted directed networks with linear or nonlinear node dynamics of various connection topologies, and with linear or nonlinear couplings.

Reconstructing links in directed networks from noisy dynamics

We address the long-standing challenge of how to reconstruct links in directed networks from measurements, and present a general method that makes use of a noise-induced relation between network structure and both the time-lagged covariance of measurements taken at two different times and the covariance of measurements taken at the same time. When the coupling functions have certain additional properties, we can further reconstruct the weights of the links.