More Like this

1. Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms

   https://doi.org/10.1145/3653723  

   Rosenkrantz, Daniel J; Marathe, Madhav V; Ravi, SS; Stearns, Richard E (June 2024, ACM Transactions on Computation Theory)

   Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Several recent articles have studied the algorithmic and complexity aspects of some decision problems on synchronous Boolean networks, which are discrete dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. Previous work has shown that some of these decision problems become efficiently solvable for systems on directed acyclic graphs (DAGs). Motivated by this line of work, we investigate a number of decision problems for dynamical systems whose underlying graphs are DAGs. We show that computational intractability (i.e.,PSPACE-completeness) results for reachability problems hold even for dynamical systems on DAGs. We also identify some restricted versions of dynamical systems on DAGs for which reachability problem can be solved efficiently. In addition, we show that a decision problem (namely, Convergence), which is efficiently solvable for dynamical systems on DAGs, becomesPSPACE-complete for Quasi-DAGs (i.e., graphs that become DAGs by the removal of asingleedge). In the process of establishing the above results, we also develop several structural properties of the phase spaces of dynamical systems on DAGs. 

   more » « less
2. Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms

   Rosenkrantz, Daniel; Marathe, Madhav; Ravi, S.S.; Stearns, Richard (May 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problem can be solved efficiently. 

   more » « less
3. Evolution of similar configurations in graph dynamical systems

   Priest, J; Marathe, M; Ravi, SS; Rosenkrantz, D; Stearns, R (December 2020, International Conference on Complex Networks and Their Applications)

   We investigate questions related to the time evolution of discrete graph dynamical systems where each node has a state from {0,1}. The configuration of a system at any time instant is a Boolean vector that specifies the state of each node at that instant. We say that two configurations are similar if the Hamming distance between them is small. Also, a predecessor of a configuration B is a configuration A such that B can be reached in one step from A. We study problems related to the similarity of predecessor configurations from which two similar configurations can be reached in one time step. We address these problems both analytically and experimentally. Our analytical results point out that the level of similarity between predecessors of two similar configurations depends on the local functions of the dynamical system. Our experimental results, which consider random graphs as well as small world networks, rely on the fact that the problem of finding predecessors can be reduced to the Boolean Satisfiability problem (SAT). 

   more » « less
4. Critical assessment of the ability of Boolean threshold models to describe gene regulatory network dynamics

   https://doi.org/10.1093/pnasnexus/pgaf228  

   Kadelka, Claus; Hari, Kishore; Benos, ed., Panayiotis (July 2025, PNAS Nexus)

   Abstract The inference of gene regulatory networks (GRNs) from high-throughput data constitutes a fundamental and challenging task in systems biology. Boolean networks are a popular modeling framework to understand the dynamic nature of GRNs. In the absence of reliable methods to infer the regulatory logic of Boolean GRN models, researchers frequently assume threshold logic as a default. Using the largest repository of published expert-curated Boolean GRN models as best proxy of reality, we systematically compare the ability of two popular threshold formalisms, the Ising and the 01 formalism, to truthfully recover biological functions and biological system dynamics. While Ising rules match fewer biological functions exactly than 01 rules, they yield a better average agreement. In general, more complex regulatory logic proves harder to be represented by either threshold formalism. Informed by these results and a meta-analysis of regulatory logic, we propose modified versions for both formalisms, which provide a better function-level and dynamic agreement with biological GRN models than the usual threshold formalisms. For small biological GRN models with low connectivity, corresponding threshold networks exhibit similar dynamics. However, they generally fail to recover the dynamics of large networks or highly connected networks. In conclusion, this study provides new insights into an important question in computational systems biology: how truthfully do Boolean threshold networks capture the dynamics of GRNs? 

   more » « less
5. Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries

   Rosenkrantz, D. J.; Adiga, A.; Marathe, M.; Qiu, Z.; Ravi, S. S.; Stearns, R.; Vullikanti, A. (June 2022, International Conference on Machine Learning)

   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