An efficient algorithm for $1$-dimensional (persistent) path homology

DOI10.1007/S00454-022-00430-8arXiv2001.09549MaRDI QIDQ6333519

Publication date: 26 January 2020

Abstract: This paper focuses on developing an efficient algorithm for analyzing a directed network (graph) from a topological viewpoint. A prevalent technique for such topological analysis involves computation of homology groups and their persistence. These concepts are well suited for spaces that are not directed. As a result, one needs a concept of homology that accommodates orientations in input space. Path-homology developed for directed graphs by Grigor'yan, Lin, Muranov and Yau has been effectively adapted for this purpose recently by Chowdhury and M'emoli. They also give an algorithm to compute this path-homology. Our main contribution in this paper is an algorithm that computes this path-homology and its persistence more efficiently for the

1

-dimensional (

H_{1}

) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the

1

-dimensional path-homnology. We implement our algorithm and present some preliminary experimental results.

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Methods of algebraic topology in functional analysis (cohomology, sheaf and bundle theory, etc.) (46M20) Relations of low-dimensional topology with graph theory (57M15) Graph algorithms (graph-theoretic aspects) (05C85)

This page was built for publication: An efficient algorithm for $1$-dimensional (persistent) path homology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333519)