论文标题
分叉图中的过滤分配
Filtration-Domination in Bifiltered Graphs
论文作者
论文摘要
Bivilter的图是一种多功能工具，用于建模二维量表的多个等级之间的数据点之间的关系。它们在拓扑数据分析中尤其流行，其中研究了诱导集团复合物的同源性能。为了减少这些集团复合物的大尺寸，我们确定了图形的过滤主导边缘，其去除保留了相关的拓扑特性。我们给出了两种算法，以检测分叉图中的过滤主导边缘并分析其复杂性。这两种算法直接在Bibilter的图上起作用，而没有先提取通常更大的集团复合物。我们提出了广泛的实验评估，这表明在大多数情况下，可以去除超过90％的边缘。反过来，我们证明，这通常会导致多参数拓扑数据分析的计算管道的大幅加速和记忆使用的减少。
Bifiltered graphs are a versatile tool for modelling relations between data points across multiple grades of a two-dimensional scale. They are especially popular in topological data analysis, where the homological properties of the induced clique complexes are studied. To reduce the large size of these clique complexes, we identify filtration-dominated edges of the graph, whose removal preserves the relevant topological properties. We give two algorithms to detect filtration-dominated edges in a bifiltered graph and analyze their complexity. These two algorithms work directly on the bifiltered graph, without first extracting the clique complexes, which are generally much bigger. We present extensive experimental evaluation which shows that in most cases, more than 90% of the edges can be removed. In turn, we demonstrate that this often leads to a substantial speedup, and reduction in the memory usage, of the computational pipeline of multiparameter topological data analysis.
