Homology theories for digraphs: statistics, applications and isomorphisms

Thesis

The persistent homology of a point cloud or finite metric space summarises the pertinent topological features in the data, as they appear and disappear when we view the data at a range of scales. Recently, there has been interest in developing persistence pipelines for directional data, such as finite quasimetric spaces or weighted digraphs, in a way that is sensitive to the data’s intrinsic asymmetry. A key ingredient in developing such a pipeline is a homology theory for digraphs. In this thesis we study two such theories: directed flag complex homology and path homology. The primary aim of this thesis is to further develop our mathematical and statistical understanding of these two homology theories, so that we may more appropriately apply them to data.

First, we seek to understand the statistical behaviour of these theories in an Erdős-Rényi random digraph model. We describe both low-density and high- density regimes in which one should expect trivial degree-1 path homology with high probability. In contrast, we show there is a medium-density regime in which one should expect non-trivial degree-1 path homology. We repeat this analysis for the directed flag complex and find similar results.

Secondly, we develop a persistence pipeline which is more directly applicable to data which takes the form of a weighted digraph. We alter persistent path homology to ensure that the number of features in the barcode coincides with the circuit rank of the digraph, and that representatives correspond to circuits in the original digraph. Using path homotopy theory, we show that the resulting pipeline is stable to a range of numerical and structural perturbations to the input weighted digraph.

Finally, through comparison with path homotopy theory, we develop a homotopy-like equivalence relation for digraph maps such that equivalent maps induce the same map on directed flag complex homology. This allows us to identify conditions under which two digraphs have isomorphic directed flag complex homology. Moreover, this equivalence allows us to obtain stability theorems for the persistent directed flag complex homology of a filtration of digraphs.

Authors: Chaplin, T

• DOI: 10.5287/ora-zbmyevnd8
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: persistent homology; path homology; digraphs; discrete homotopy; directed flag complex; topological data analysis; stochastic topology
• Subjects: Mathematics