Extracting connectivity from dynamics of networks with uniform bidirectional coupling

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.

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.

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.

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.

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.

High-resolution directed human connectomes and the Consensus Connectome Dynamics

Here we show a method of directing the edges of the connectomes, prepared from HARDI datasets from the human brain. Before the present work, no high-definition directed braingraphs were published, because the tractography methods in use are not capable of assigning directions to the neural tracts discovered. Previous work on the functional connectomes applied low-resolution functional MRI-detected statistical causality for the assignment of directions of connectomes of typically several dozens of vertices. Our method is based on the phenomenon of the “Consensus Connectome Dynamics”, described earlier by our research group. In this contribution, we apply the method to the 423 braingraphs, each with 1015 vertices, computed from the public release of the Human Connectome Project, and we also made the directed connectomes publicly available at the site http://braingraph.org. We also show the robustness of our edge directing method in four independently chosen connectome datasets: we have found that 86% of the edges, which were present in all four datasets, get the same directions in all datasets; therefore the direction method is robust. While our new edge-directing method still needs more empirical validation, we think that our present contribution opens up new possibilities in the analysis of the high-definition human connectome.

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.

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.

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.

Recovery of couplings and parameters of elements in networks of time-delay systems from time series

We propose a method for the recovery of coupling architecture and the parameters of elements in networks consisting of coupled oscillators described by delay-differential equations. For each oscillator in the network, we introduce an objective function characterizing the distance between the points of the reconstructed nonlinear function. The proposed method is based on the minimization of this objective function and the separation of the recovered coupling coefficients into significant and insignificant coefficients. The efficiency of the method is shown for chaotic time series generated by model equations of diffusively coupled time-delay systems and for experimental chaotic time series gained from coupled electronic oscillators with time-delayed feedback.

Estimation of Directed Effective Connectivity from fMRI Functional Connectivity Hints at Asymmetries of Cortical Connectome

The brain exhibits complex spatio-temporal patterns of activity. This phenomenon is governed by an interplay between the internal neural dynamics of cortical areas and their connectivity. Uncovering this complex relationship has raised much interest, both for theory and the interpretation of experimental data (e.g., fMRI recordings) using dynamical models. Here we focus on the so-called inverse problem: the inference of network parameters in a cortical model to reproduce empirically observed activity. Although it has received a lot of interest, recovering directed connectivity for large networks has been rather unsuccessful so far. The present study specifically addresses this point for a noise-diffusion network model. We develop a Lyapunov optimization that iteratively tunes the network connectivity in order to reproduce second-order moments of the node activity, or functional connectivity. We show theoretically and numerically that the use of covariances with both zero and non-zero time shifts is the key to infer directed connectivity. The first main theoretical finding is that an accurate estimation of the underlying network connectivity requires that the time shift for covariances is matched with the time constant of the dynamical system. In addition to the network connectivity, we also adjust the intrinsic noise received by each network node. The framework is applied to experimental fMRI data recorded for subjects at rest. Diffusion-weighted MRI data provide an estimate of anatomical connections, which is incorporated to constrain the cortical model. The empirical covariance structure is reproduced faithfully, especially its temporal component (i.e., time-shifted covariances) in addition to the spatial component that is usually the focus of studies. We find that the cortical interactions, referred to as effective connectivity, in the tuned model are not reciprocal. In particular, hubs are either receptors or feeders: they do not exhibit both strong incoming and outgoing connections. Our results sets a quantitative ground to explore the propagation of activity in the cortex.

The study of interactions between different cortical regions at rest or during a task has considerably developed in the past decades thanks to progress in non-invasive imaging techniques, such as fMRI, EEG and MEG. These techniques have revealed that distant cortical areas exhibit specific correlated activity during the resting state, also called functional connectivity (FC). Moreover, recent studies have highlighted the possible role of white-matter projections between cortical regions in shaping these activity patterns. This structural connectivity (SC) can be estimated using MRI, which measures the probability for two areas to be connected via the density of neural fibers. However, this does not provide the strengths of dynamical interactions. Many methods have thus been developed to estimate the connectivity between neural populations in the cortex that is hypothesized to shape FC. The strengths of these dynamical interactions are called effective connectivity (EC). We use a cortical model that combines information from Diffusion-weighted MRI (dwMRI) and fMRI in order to estimate EC. We demonstrate theoretically that directed C can be inferred using time-shifted covariances. The key point of our method is the use of temporal information from FC at the scale of the whole network. Applying our model on experimental fMRI data at rest, we estimate the asymmetry of intracortical connectivity. Obtaining an accurate EC estimate is essential to analyze its graph properties, such as hubs. In particular, directed connectivity links to the asymmetry between input and output EC strengths of each node, which characterizes feeder and receiver hubs in the cortical network.

Inferring the connectivity of coupled oscillators from time-series statistical similarity analysis

A system composed by interacting dynamical elements can be represented by a network, where the nodes represent the elements that constitute the system, and the links account for their interactions, which arise due to a variety of mechanisms, and which are often unknown. A popular method for inferring the system connectivity (i.e., the set of links among pairs of nodes) is by performing a statistical similarity analysis of the time-series collected from the dynamics of the nodes. Here, by considering two systems of coupled oscillators (Kuramoto phase oscillators and Rössler chaotic electronic oscillators) with known and controllable coupling conditions, we aim at testing the performance of this inference method, by using linear and non linear statistical similarity measures. We find that, under adequate conditions, the network links can be perfectly inferred, i.e., no mistakes are made regarding the presence or absence of links. These conditions for perfect inference require: i) an appropriated choice of the observed variable to be analysed, ii) an appropriated interaction strength, and iii) an adequate thresholding of the similarity matrix. For the dynamical units considered here we find that the linear statistical similarity measure performs, in general, better than the non-linear ones.

Synchronization properties of heterogeneous neuronal networks with mixed excitability type

We study the synchronization of neuronal networks with dynamical heterogeneity, showing that network structures with the same propensity for synchronization (as quantified by master stability function analysis) may develop dramatically different synchronization properties when heterogeneity is introduced with respect to neuronal excitability type. Specifically, we investigate networks composed of neurons with different types of phase response curves (PRCs), which characterize how oscillating neurons respond to excitatory perturbations. Neurons exhibiting type 1 PRC respond exclusively with phase advances, while neurons exhibiting type 2 PRC respond with either phase delays or phase advances, depending on when the perturbation occurs. We find that Watts-Strogatz small world networks transition to synchronization gradually as the proportion of type 2 neurons increases, whereas scale-free networks may transition gradually or rapidly, depending upon local correlations between node degree and excitability type. Random placement of type 2 neurons results in gradual transition to synchronization, whereas placement of type 2 neurons as hubs leads to a much more rapid transition, showing that type 2 hub cells easily "hijack" neuronal networks to synchronization. These results underscore the fact that the degree of synchronization observed in neuronal networks is determined by a complex interplay between network structure and the dynamical properties of individual neurons, indicating that efforts to recover structural connectivity from dynamical correlations must in general take both factors into account.

Reconstructing weighted networks from dynamics

We present a method that reconstructs both the links and their relative coupling strength of bidirectional weighted networks. Our method requires only measurements of node dynamics as input. Using several examples, we demonstrate that our method can give accurate results for weighted random and weighted scale-free networks with both linear and nonlinear dynamics.

Solving the inverse problem of noise-driven dynamic networks

Nowadays, massive amounts of data are available for analysis in natural and social systems and the tasks to depict system structures from the data, i.e., the inverse problems, become one of the central issues in wide interdisciplinary fields. In this paper, we study the inverse problem of dynamic complex networks driven by white noise. A simple and universal inference formula of double correlation matrices and noise-decorrelation (DCMND) method is derived analytically, and numerical simulations confirm that the DCMND method can accurately depict both network structures and noise correlations by using available output data only. This inference performance has never been regarded possible by theoretical derivation, numerical computation, and experimental design.

Reconstruction of network structures from repeating spike patterns in simulated bursting dynamics

Repeating patterns of spike sequences from a neuronal network have been proposed to be useful in the reconstruction of the network topology. Reverberations in a physiologically realistic model with various physical connection topologies (from random to scale free) have been simulated to study the effectiveness of the pattern-matching method in the reconstruction of network topology from network dynamics. Simulation results show that functional networks reconstructed from repeating spike patterns can be quite different from the original physical networks; even global properties, such as the degree distribution, cannot always be recovered. However, the pattern-matching method can be effective in identifying hubs in the network. Since the form of reverberations is quite different for networks with and without hubs, the form of reverberations together with the reconstruction by repeating spike patterns might provide a reliable method to detect hubs in neuronal cultures.