More Like this

1. Using Zigzag Persistent Homology to Detect Hopf Bifurcations in Dynamical Systems

   https://doi.org/10.3390/a13110278  

   Tymochko, Sarah; Munch, Elizabeth; Khasawneh, Firas A. (November 2020, Algorithms)

   null (Ed.)

   Bifurcations in dynamical systems characterize qualitative changes in the system behavior. Therefore, their detection is important because they can signal the transition from normal system operation to imminent failure. In an experimental setting, this transition could lead to incorrect data or damage to the entire experiment. While standard persistent homology has been used in this setting, it usually requires analyzing a collection of persistence diagrams, which in turn drives up the computational cost considerably. Using zigzag persistence, we can capture topological changes in the state space of the dynamical system in only one persistence diagram. Here, we present Bifurcations using ZigZag (BuZZ), a one-step method to study and detect bifurcations using zigzag persistence. The BuZZ method is successfully able to detect this type of behavior in two synthetic examples as well as an example dynamical system. 

   more » « less
2. An Adjacency Matrix Approach to Delay Analysis in Temporal Networks

   Shea, John M.; Macker, Joseph P. (January 2017, MILCOM IEEE Military Communications Conference)

   Wireless communications networks are often mod- eled as graphs in which the vertices represent wireless devices and the edges represent the communication links between them. However, graphs fail to capture the time-varying nature of wire- less networks. Temporal networks are graphs in which the sets of nodes or edges are time-varying. We consider the most common case, in which the set of nodes is fixed but the presence of edges changes over time. Most previous work on analyzing temporal networks has focused on summary measures that combine the contributions of different paths by using different weights for paths with different delays. Such summary measures are efficient to compute but may lose valuable information about the temporal behavior of the network. We propose techniques that characterize the delays of all paths between nodes in temporal networks. We then apply these techniques to identify dominant patterns in the temporal paths connecting nodes. Example temporal networks are used to illustrate these phenomena, and we consider implications to wireless networks. 

   more » « less
3. Computing Zigzag Persistence on Graphs in Near-Linear Time

   https://doi.org/10.4230/LIPIcs.SoCG.2021.30  

   Dey, Tamal; Hou, Tao (June 2021, Leibniz international proceedings in informatics)

   null (Ed.)

   Graphs model real-world circumstances in many applications where they may constantly change to capture the dynamic behavior of the phenomena. Topological persistence which provides a set of birth and death pairs for the topological features is one instrument for analyzing such changing graph data. However, standard persistent homology defined over a growing space cannot always capture such a dynamic process unless shrinking with deletions is also allowed. Hence, zigzag persistence which incorporates both insertions and deletions of simplices is more appropriate in such a setting. Unlike standard persistence which admits nearly linear-time algorithms for graphs, such results for the zigzag version improving the general O(m^ω) time complexity are not known, where ω < 2.37286 is the matrix multiplication exponent. In this paper, we propose algorithms for zigzag persistence on graphs which run in near-linear time. Specifically, given a filtration with m additions and deletions on a graph with n vertices and edges, the algorithm for 0-dimension runs in O(mlog² n+mlog m) time and the algorithm for 1-dimension runs in O(mlog⁴ n) time. The algorithm for 0-dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2-manifolds. The algorithm for 1-dimension pairs a negative edge with the earliest positive edge so that a 1-cycle containing both edges resides in all intermediate graphs. Both algorithms achieve the claimed time complexity via dynamic graph data structures proposed by Holm et al. In the end, using Alexander duality, we extend the algorithm for 0-dimension to compute the (p-1)-dimensional zigzag persistence for ℝ^p-embedded complexes in O(mlog² n+mlog m+nlog n) time. 

   more » « less
4. Inferring Dynamic Regulatory Interaction Graphs From Time Series Data With Perturbations

   Bhaskar, D; Magruder, Daniel S; Morales, M; De_Brouwer, E; Venkat, A; Wenkel, F; Noonan, J; Wolf, G; Ivanova, N; Krishnaswamy, S (April 2024, PMLR)

   Complex systems are characterized by intricate interactions between entities that evolve dynamically over time. Accurate inference of these dynamic relationships is crucial for understanding and predicting system behavior. In this paper, we propose Regulatory Temporal Interaction Network Inference (RiTINI) for inferring time-varying interaction graphs in complex systems using a novel combination of space-and-time graph attentions and graph neural ordinary differential equations (ODEs). RiTINI leverages time-lapse signals on a graph prior, as well as perturbations of signals at various nodes in order to effectively capture the dynamics of the underlying system. This approach is distinct from traditional causal inference networks, which are limited to inferring acyclic and static graphs. In contrast, RiTINI can infer cyclic, directed, and time-varying graphs, providing a more comprehensive and accurate representation of complex systems. The graph attention mechanism in RiTINI allows the model to adaptively focus on the most relevant interactions in time and space, while the graph neural ODEs enable continuous-time modeling of the system’s dynamics. We evaluate RiTINI’s performance on simulations of dynamical systems, neuronal networks, and gene regulatory networks, demonstrating its state-of-the-art capability in inferring interaction graphs compared to previous methods. 

   more » « less
5. Fast Computation of Zigzag Persistence

   Dey, T. K.; Hou, T. (November 2022, LIPIcs, Volume 244, ESA 2022, Complete Volume)

   Zigzag persistence is a powerful extension of the standard persistence which allows deletions of simplices besides insertions. However, computing zigzag persistence usually takes considerably more time than the standard persistence. We propose an algorithm called FastZigzag which narrows this efficiency gap. Our main result is that an input simplex-wise zigzag filtration can be converted to a cell-wise non-zigzag filtration of a ∆-complex with the same length, where the cells are copies of the input simplices. This conversion step in FastZigzag incurs very little cost. Furthermore, the barcode of the original filtration can be easily read from the barcode of the new cell-wise filtration because the conversion embodies a series of diamond switches known in topological data analysis. This seemingly simple observation opens up the vast possibilities for improving the computation of zigzag persistence because any efficient algorithm/software for standard persistence can now be applied to computing zigzag persistence. Our experiment shows that this indeed achieves substantial performance gain over the existing state-of-the-art softwares. 

   more » « less