Reconstructing links in directed networks from noisy dynamics

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.

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.

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.

Heterogeneous Responses to Changes in Inhibitory Synaptic Strength in Networks of Spiking Neurons

How does the dynamics of neurons in a network respond to changes in synaptic weights? Answer to this question would be important for a full understanding of synaptic plasticity. In this article, we report our numerical study of the effects of changes in inhibitory synaptic weights on the spontaneous activity of networks of spiking neurons with conductance-based synapses. Networks with biologically realistic features, which were reconstructed from multi-electrode array recordings taken in a cortical neuronal culture, and their modifications were used in the simulations. The magnitudes of the synaptic weights of all the inhibitory connections are decreased by a uniform amount subjecting to the condition that inhibitory connections would not be turned into excitatory ones. Our simulation results reveal that the responses of the neurons are heterogeneous: while the firing rate of some neurons increases as expected, the firing rate of other neurons decreases or remains unchanged. The same results show that heterogeneous responses also occur for an enhancement of inhibition. This heterogeneity in the responses of neurons to changes in inhibitory synaptic strength suggests that activity-induced modification of synaptic strength does not necessarily generate a positive feedback loop on the dynamics of neurons connected in a network. Our results could be used to understand the effects of bicuculline on spiking and bursting activities of neuronal cultures. Using reconstructed networks with biologically realistic features enables us to identify a long-tailed distribution of average synaptic weights for outgoing links as a crucial feature in giving rise to bursting in neuronal networks and in determining the overall response of the whole network to changes in synaptic strength. For networks whose average synaptic weights for outgoing links have a long-tailed distribution, bursting is observed and the average firing rate of the whole network increases upon inhibition suppression or decreases upon inhibition enhancement. For networks whose average synaptic weights for outgoing links are approximately normally distributed, bursting is not found and the average firing rate of the whole network remains approximately constant upon changes in inhibitory synaptic strength.

The reconstruction on the game networks with binary-state and multi-state dynamics

Reconstruction of network is to infer the relationship among nodes using observation data, which is helpful to reveal properties and functions of complex systems. In view of the low reconstruction accuracy based on small data and the subjectivity of threshold to infer adjacency matrix, the paper proposes two models: the quadratic compressive sensing (QCS) and integer compressive sensing (ICS). Then a combined method (CCS) is given based on QCS and ICS, which can be used on binary-state and multi-state dynamics. It is found that CCS is usually a superior method comparing with compressive sensing, LASSO on several networks with different structures and scales. And it can infer larger node correctly than the other two methods. The paper is conducive to reveal the hidden relationship with small data so that to understand, predicate and control a vast intricate system.

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.

Reconstructing network structures from partial measurements

The dynamics of systems of interacting agents is determined by the structure of their coupling network. The knowledge of the latter is, therefore, highly desirable, for instance, to develop efficient control schemes, to accurately predict the dynamics, or to better understand inter-agent processes. In many important and interesting situations, the network structure is not known, however, and previous investigations have shown how it may be inferred from complete measurement time series on each and every agent. These methods implicitly presuppose that, even though the network is not known, all its nodes are. Here, we investigate the different problem of inferring network structures within the observed/measured agents. For symmetrically coupled dynamical systems close to a stable equilibrium, we establish analytically and illustrate numerically that velocity signal correlators encode not only direct couplings, but also geodesic distances in the coupling network within the subset of measurable agents. When dynamical data are accessible for all agents, our method is furthermore algorithmically more efficient than the traditional ones because it does not rely on matrix inversion.

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.

Detecting network structures from measurable data produced by dynamics with hidden variables

Depicting network structures from measurable data is of significance. In real-world situations, it is common that some variables of networks are unavailable or even unknown. These unavailable and unknown variables, i.e., hidden variables, will lead to much reconstruction error, even make reconstruction methods useless. In this paper, to solve hidden variable problems, we propose three reconstruction methods, respectively, based on the following conditions: statistical characteristics of hidden variables, linearizable hidden variables, and white noise injection. Among them, the method based on white noise injection is active and invasive. In our framework, theoretic analyses of these three methods are given at first, and, furthermore, the validity of theoretical derivations and the robustness of these methods are fully verified through numerical results. Our work may be, therefore, helpful for practical experiments.

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.

Determination of effective brain connectivity from activity correlations

Effective connectivity embodied in transfer functions is derived from symmetric-network activity correlations under task-free conditions via a recent causal spectral factorization method. This generalizes previous covariance-based analyses to include frequency dependencies and time delays. Results are verified against analytic solutions of equations that have reproduced many aspects of experimental brain dynamics and against cases of more complex connectivity. Robustness to noise is also demonstrated.

Estimating the impact of structural directionality: How reliable are undirected connectomes?

Directionality is a fundamental feature of network connections. Most structural brain networks are intrinsically directed because of the nature of chemical synapses, which comprise most neuronal connections. Because of the limitations of noninvasive imaging techniques, the directionality of connections between structurally connected regions of the human brain cannot be confirmed. Hence, connections are represented as undirected, and it is still unknown how this lack of directionality affects brain network topology. Using six directed brain networks from different species and parcellations (cat, mouse, C. elegans, and three macaque networks), we estimate the inaccuracies in network measures (degree, betweenness, clustering coefficient, path length, global efficiency, participation index, and small-worldness) associated with the removal of the directionality of connections. We employ three different methods to render directed brain networks undirected: (a) remove unidirectional connections, (b) add reciprocal connections, and (c) combine equal numbers of removed and added unidirectional connections. We quantify the extent of inaccuracy in network measures introduced through neglecting connection directionality for individual nodes and across the network. We find that the coarse division between core and peripheral nodes remains accurate for undirected networks. However, hub nodes differ considerably when directionality is neglected. Comparing the different methods to generate undirected networks from directed ones, we generally find that the addition of reciprocal connections (false positives) causes larger errors in graph-theoretic measures than the removal of the same number of directed connections (false negatives). These findings suggest that directionality plays an essential role in shaping brain networks and highlight some limitations of undirected connectomes.

Modeling of cytometry data in logarithmic space: When is a bimodal distribution not bimodal?

Recent efforts in systems immunology lead researchers to build quantitative models of cell activation and differentiation. One goal is to account for the distributions of proteins from single-cell measurements by flow cytometry or mass cytometry as readout of biological regulation. In that context, large cell-to-cell variability is often observed in biological quantities. We show here that these readouts, viewed in logarithmic scale may result in two easily-distinguishable modes, while the underlying distribution (in linear scale) is unimodal. We introduce a simple mathematical test to highlight this mismatch. We then dissect the flow of influence of cell-to-cell variability proposing a graphical model which motivates higher-dimensional analysis of the data. Finally we show how acquiring additional biological information can be used to reduce uncertainty introduced by cell-to-cell variability, helping to clarify whether the data is uni- or bimodal. This communication has cautionary implications for manual and automatic gating strategies, as well as clustering and modeling of single-cell measurements. © 2018 International Society for Advancement of Cytometry.

Model-free inference of direct network interactions from nonlinear collective dynamics

The topology of interactions in network dynamical systems fundamentally underlies their function. Accelerating technological progress creates massively available data about collective nonlinear dynamics in physical, biological, and technological systems. Detecting direct interaction patterns from those dynamics still constitutes a major open problem. In particular, current nonlinear dynamics approaches mostly require to know a priori a model of the (often high dimensional) system dynamics. Here we develop a model-independent framework for inferring direct interactions solely from recording the nonlinear collective dynamics generated. Introducing an explicit dependency matrix in combination with a block-orthogonal regression algorithm, the approach works reliably across many dynamical regimes, including transient dynamics toward steady states, periodic and non-periodic dynamics, and chaos. Together with its capabilities to reveal network (two point) as well as hypernetwork (e.g., three point) interactions, this framework may thus open up nonlinear dynamics options of inferring direct interaction patterns across systems where no model is known.

Network dynamical systems can represent the interactions involved in the collective dynamics of gene regulatory networks or metabolic circuits. Here Casadiego et al. present a method for inferring these types of interactions directly from observed time series without relying on their model.

Transition to reconstructibility in weakly coupled networks

Across scientific disciplines, thresholded pairwise measures of statistical dependence between time series are taken as proxies for the interactions between the dynamical units of a network. Yet such correlation measures often fail to reflect the underlying physical interactions accurately. Here we systematically study the problem of reconstructing direct physical interaction networks from thresholding correlations. We explicate how local common cause and relay structures, heterogeneous in-degrees and non-local structural properties of the network generally hinder reconstructibility. However, in the limit of weak coupling strengths we prove that stationary systems with dynamics close to a given operating point transition to universal reconstructiblity across all network topologies.

Large order fluctuations, switching, and control in complex networks

We propose an analytical technique to study large fluctuations and switching from internal noise in complex networks. Using order-disorder kinetics as a generic example, we construct and analyze the most probable, or optimal path of fluctuations from one ordered state to another in real and synthetic networks. The method allows us to compute the distribution of large fluctuations and the time scale associated with switching between ordered states for networks consistent with mean-field assumptions. In general, we quantify how network heterogeneity influences the scaling patterns and probabilities of fluctuations. For instance, we find that the probability of a large fluctuation near an order-disorder transition decreases exponentially with the participation ratio of a network's principle eigenvector - measuring how many nodes effectively contribute to an ordered state. Finally, the proposed theory is used to answer how and where a network should be targeted in order to optimize the time needed to observe a switch.

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.