Abstract
This thesis exposes a link between two previously distinct mathematical structures, both of which are used to represent nonlinear time series in a growing number of scientific applications: the horizontal visibility graph (HVG) and the sub level set merge tree which underpins topological data analysis (TDA)and persistent homology barcodes. These representations have evolved independently, and each now has its own substantial body of literature. Nevertheless, we show that for ordered data,HVGs and barcodes actually emerge from the same underlying structure. They respectively capture combinatorial and stable metric properties of objects we introduce and study: the discrete time series merge tree and its plane dual the horizon visibility graph.The main mathematical result is that there exists a planarduality between our newly introduced horizon visibility graph and the sublevel set merge tree over a discrete time series. In this context classical HVGs are shown to be weak planar duals f (the one-point compactification of) the merge tree, while our horizon visibility graphs are strong planar duals. Thus, HVG scapture combinatorial properties of merge trees over time series while, dually, sub level set persistence diagrams capture stable metric properties of merge trees over time series.
The thesis then explores some immediate consequences of the noted duality. In one direction, we use properties of topological merge trees to derive efficient distributed algorithms for horizontal visibility graph construction, outperforming all previous methods. In the other direction, we leverage known results on properties of HVGs over chaotic trajectories to propose a range of new measures for chaos detection based on super level and sub level merge trees, our topological divergences. Using these measures as features in machine learning pipelines for chaos detection and quantification leads to improved performance compared with existing baselines from the topological data analysis (TDA) and horizontal visibility graph (HVG)literature.
The original authors of the horizontal visibility graph approach in 2010 admitted that finding the core of a formal theory for it would be a challenging research program likely to entangle dynamical systems and graph theory together. This thesis argues that their approach is best viewed as an entanglement between dynamical systems and metric trees describing topological filtrations over path graphs associated to trajectories. It shows why this is the case, through a graph duality, and begins to explore some of the practical consequences of the correspondence between horizontal visibility and merge trees.
| Date of Award | Feb 2025 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | James Griffin (Supervisor) & Matthew England (Supervisor) |