An official website of the United States government
Many papers have addressed the problem of learning the behavior (i.e., the local interaction function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the network topology and the behavior of such a system through active queries. Our results are for systems where the state of each node is from {0, 1} and the local functions are Boolean. We present inference algorithms under both batch and adaptive query models for dynamical systems with symmetric local functions. These algorithms show that the structure and behavior of such dynamical systems can be learnt using only a polynomial number of queries. Further, we establish a lower bound on the number of queries needed to learn such dynamical systems. We also present experimental results obtained by running our algorithms on synthetic and real-world networks.
more »
« less
Breaking reflection symmetry: evolving long dynamical cycles in Boolean systems
Abstract In interacting dynamical systems, specific local interaction rules for system components give rise to diverse and complex global dynamics. Long dynamical cycles are a key feature of many natural interacting systems, especially in biology. Examples of dynamical cycles range from circadian rhythms regulating sleep to cell cycles regulating reproductive behavior. Despite the crucial role of cycles in nature, the properties of network structure that give rise to cycles still need to be better understood. Here, we use a Boolean interaction network model to study the relationships between network structure and cyclic dynamics. We identify particular structural motifs that support cycles, and other motifs that suppress them. More generally, we show that the presence ofdynamical reflection symmetryin the interaction network enhances cyclic behavior. In simulating an artificial evolutionary process, we find that motifs that break reflection symmetry are discarded. We further show that dynamical reflection symmetries are over-represented in Boolean models of natural biological systems. Altogether, our results demonstrate a link between symmetry and functionality for interacting dynamical systems, and they provide evidence for symmetry’s causal role in evolving dynamical functionality.
more »
« less
- Award ID(s):
- 2309043
- PAR ID:
- 10489720
- Publisher / Repository:
- IOP Publishing
- Date Published:
- Journal Name:
- New Journal of Physics
- Volume:
- 26
- Issue:
- 2
- ISSN:
- 1367-2630
- Format(s):
- Medium: X Size: Article No. 023006
- Size(s):
- Article No. 023006
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Rainey, Larry B.; Holland, O. Thomas (Ed.)Biological neural networks offer some of the most striking and complex examples of emergence ever observed in natural or man-made systems. Individually, the behavior of a single neuron is rather simple, yet these basic building blocks are connected through synapses to form neural networks, which are capable of sophisticated capabilities such as pattern recognition and navigation. Lower-level functionality provided by a given network is combined with other networks to produce more sophisticated capabilities. These capabilities manifest emergently at two vastly different, yet interconnected time scales. At the time scale of neural dynamics, neural networks are responsible for turning noisy external stimuli and internal signals into signals capable of supporting complex computations. A key component in this process is the structure of the network, which itself forms emergently over much longer time scales based on the outputs of its constituent neurons, a process called learning. The analysis and interpretation of the behaviors of these interconnected dynamical systems of neurons should account for the network structure and the collective behavior of the network. The field of graph signal processing (GSP) combines signal processing with network science to study signals defined on irregular network structures. Here, we show that GSP can be a valuable tool in the analysis of emergence in biological neural networks. Beyond any purely scientific pursuits, understanding the emergence in biological neural networks directly impacts the design of more effective artificial neural networks for general machine learning and artificial intelligence tasks across domains, and motivates additional design motifs for novel emergent systems of systems.more » « less
-
Cellular fates are determined by genes interacting across large, complex biological networks. A critical question is how to identify causal relationships spanning distinct signaling pathways and underlying organismal phenotypes. Here, we address this question by constructing a Boolean model of a well-studied developmental network and analyzing information flows through the system. Depending on environmental signals Caenorhabditis elegans develop normally to sexual maturity or enter a reproductively delayed, developmentally quiescent ‘dauer’ state, progressing to maturity when the environment changes. The developmental network that starts with environmental signal and ends in the dauer/no dauer fate involves genes across 4 signaling pathways including cyclic GMP, Insulin/IGF-1, TGF- β and steroid hormone synthesis. We identified three stable motifs leading to normal development, each composed of genes interacting across the Insulin/IGF-1, TGF- β and steroid hormone synthesis pathways. Three genes known to influence dauer fate, daf-2 , daf-7 and hsf-1 , acted as driver nodes in the system. Using causal logic analysis, we identified a five gene cyclic subgraph integrating the information flow from environmental signal to dauer fate. Perturbation analysis showed that a multifactorial insulin profile determined the stable motifs the system entered and interacted with daf-12 as the switchpoint driving the dauer/no dauer fate. Our results show that complex organismal systems can be distilled into abstract representations that permit full characterization of the causal relationships driving developmental fates. Analyzing organismal systems from this perspective of logic and function has important implications for studies examining the evolution and conservation of signaling pathways.more » « less
-
Kryven, Ivan (Ed.)Combinatorial threshold-linear networks (CTLNs) are a special class of inhibition-dominated TLNs defined from directed graphs. Like more general TLNs, they display a wide variety of nonlinear dynamics including multistability, limit cycles, quasiperiodic attractors, and chaos. In prior work, we have developed a detailed mathematical theory relating stable and unstable fixed points of CTLNs to graph-theoretic properties of the underlying network. Here we find that a special type of fixed points, corresponding to core motifs , are predictive of both static and dynamic attractors. Moreover, the attractors can be found by choosing initial conditions that are small perturbations of these fixed points. This motivates us to hypothesize that dynamic attractors of a network correspond to unstable fixed points supported on core motifs. We tested this hypothesis on a large family of directed graphs of size n = 5, and found remarkable agreement. Furthermore, we discovered that core motifs with similar embeddings give rise to nearly identical attractors. This allowed us to classify attractors based on structurally-defined graph families. Our results suggest that graphical properties of the connectivity can be used to predict a network’s complex repertoire of nonlinear dynamics.more » « less
-
Abstract Population cycles are fundamentally linked with spatial synchrony, the prevailing paradigm being that populations with cyclic dynamics are easily synchronised. That is, population cycles help give rise to spatial synchrony. Here we demonstrate this process can work in reverse, with synchrony causing population cycles. We show that timescale‐specific environmental effects, by synchronising local population dynamics on certain timescales only, cause major population cycles over large areas in white‐tailed deer. An important aspect of the new mechanism is specificity of synchronising effects to certain timescales, which causes local dynamics to sum across space to a substantial cycle on those timescales. We also demonstrate, to our knowledge for the first time, that synchrony can be transmitted not only from environmental drivers to populations (deer), but also from there to human systems (deer‐vehicle collisions). Because synchrony of drivers may be altered by climate change, changes to population cycles may arise via our mechanism.more » « less
