论文标题
高效算法，价格为$ 1 $二维（持久）路径同源性
An efficient algorithm for $1$-dimensional (persistent) path homology
论文作者
论文摘要
本文着重于开发一种从拓扑观点分析有向网络（图）的有效算法。这种拓扑分析的普遍技术涉及同源组及其持久性的计算。这些概念非常适合非指示的空间。结果，需要一个同源概念，以适应输入空间中的方向。 Grigor'yan，Lin，Muranov和Yau为定向图开发的路径 - 理论最近已被Chowdhury和Mémoli有效地为此目的。他们还提供了一种算法来计算这种路径学。我们在本文中的主要贡献是一种算法，该算法可以针对$ 1 $维（$ h_1 $）的情况更有效地计算此路径学及其持久性。在开发这样的算法时，我们发现了各种结构及其有效计算，以帮助计算$ 1 $维的路径 - 同理学。我们实施算法并提出一些初步的实验结果。
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émoli. 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.
