Abstract
Bifiltered graphs are a versatile tool for modelling relations between data points across multiple grades of a twodimensional 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.
Original language | English |
---|---|
Title of host publication | 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2023 |
Publisher | Society for Industrial and Applied Mathematics Publications |
Pages | 27-38 |
Number of pages | 12 |
ISBN (Electronic) | 9781611977561 |
Publication status | Published - 2023 |
Event | 2023 SIAM Symposium on Algorithm Engineering and Experiments: ALENEX 2023 - Florence, Virtual, Italy Duration: 22 Jan 2023 → 23 Jan 2023 |
Conference
Conference | 2023 SIAM Symposium on Algorithm Engineering and Experiments |
---|---|
Country/Territory | Italy |
City | Florence, Virtual |
Period | 22/01/23 → 23/01/23 |
ASJC Scopus subject areas
- General Engineering
- Applied Mathematics