Research

27 pages, 4581 KiB

Open AccessArticle

From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives

by Lida Kanari, Adélie Garin and Kathryn Hess

Algorithms 2020, 13(12), 335; https://0-doi-org.brum.beds.ac.uk/10.3390/a13120335 - 11 Dec 2020

Cited by 8 | Viewed by 3129

Methods of topological data analysis have been successfully applied in a wide range of fields to provide useful summaries of the structure of complex data sets in terms of topological descriptors, such as persistence diagrams. While there are many powerful techniques for computing [...] Read more.

Methods of topological data analysis have been successfully applied in a wide range of fields to provide useful summaries of the structure of complex data sets in terms of topological descriptors, such as persistence diagrams. While there are many powerful techniques for computing topological descriptors, the inverse problem, i.e., recovering the input data from topological descriptors, has proved to be challenging. In this article, we study in detail the Topological Morphology Descriptor (TMD), which assigns a persistence diagram to any tree embedded in Euclidean space, and a sort of stochastic inverse to the TMD, the Topological Neuron Synthesis (TNS) algorithm, gaining both theoretical and computational insights into the relation between the two. We propose a new approach to classify barcodes using symmetric groups, which provides a concrete language to formulate our results. We investigate to what extent the TNS recovers a geometric tree from its TMD and describe the effect of different types of noise on the process of tree generation from persistence diagrams. We prove moreover that the TNS algorithm is stable with respect to specific types of noise. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

15 pages, 1180 KiB

Open AccessArticle

Lumáwig: An Efficient Algorithm for Dimension Zero Bottleneck Distance Computation in Topological Data Analysis

by Paul Samuel Ignacio, Jay-Anne Bulauan and David Uminsky

Algorithms 2020, 13(11), 291; https://0-doi-org.brum.beds.ac.uk/10.3390/a13110291 - 11 Nov 2020

Cited by 3 | Viewed by 3369

Abstract

Stability of persistence diagrams under slight perturbations is a key characteristic behind the validity and growing popularity of topological data analysis in exploring real-world data. Central to this stability is the use of Bottleneck distance which entails matching points between diagrams. Instances of [...] Read more.

Stability of persistence diagrams under slight perturbations is a key characteristic behind the validity and growing popularity of topological data analysis in exploring real-world data. Central to this stability is the use of Bottleneck distance which entails matching points between diagrams. Instances of use of this metric in practical studies have, however, been few and sparingly far between because of the computational obstruction, especially in dimension zero where the computational cost explodes with the growth of data size. We present a novel efficient algorithm to compute dimension zero bottleneck distance between two persistent diagrams of a specific kind which runs significantly faster and provides significantly sharper approximates with respect to the output of the original algorithm than any other available algorithm. We bypass the overwhelming matching problem in previous implementations of the bottleneck distance, and prove that the zero dimensional bottleneck distance can be recovered from a very small number of matching cases. Partly in keeping with nomenclature traditions in this area of TDA, we name this algorithm Lumáwig as a nod to a deity in the northern Philippines, where the algorithm was developed. We show that Lumáwig generally enjoys linear complexity as shown by empirical tests. We also present an application that leverages dimension zero persistence diagrams and the bottleneck distance to produce features for classification tasks. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

13 pages, 3892 KiB

Open AccessArticle

Using Zigzag Persistent Homology to Detect Hopf Bifurcations in Dynamical Systems

by Sarah Tymochko, Elizabeth Munch and Firas A. Khasawneh

Algorithms 2020, 13(11), 278; https://0-doi-org.brum.beds.ac.uk/10.3390/a13110278 - 31 Oct 2020

Cited by 10 | Viewed by 3564

Abstract

Bifurcations in dynamical systems characterize qualitative changes in the system behavior. Therefore, their detection is important because they can signal the transition from normal system operation to imminent failure. In an experimental setting, this transition could lead to incorrect data or damage to [...] Read more.

Bifurcations in dynamical systems characterize qualitative changes in the system behavior. Therefore, their detection is important because they can signal the transition from normal system operation to imminent failure. In an experimental setting, this transition could lead to incorrect data or damage to the entire experiment. While standard persistent homology has been used in this setting, it usually requires analyzing a collection of persistence diagrams, which in turn drives up the computational cost considerably. Using zigzag persistence, we can capture topological changes in the state space of the dynamical system in only one persistence diagram. Here, we present Bifurcations using ZigZag (BuZZ), a one-step method to study and detect bifurcations using zigzag persistence. The BuZZ method is successfully able to detect this type of behavior in two synthetic examples as well as an example dynamical system. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

30 pages, 14630 KiB

Open AccessArticle

An Efficient Data Retrieval Parallel Reeb Graph Algorithm

by Mustafa Hajij and Paul Rosen

Algorithms 2020, 13(10), 258; https://0-doi-org.brum.beds.ac.uk/10.3390/a13100258 - 12 Oct 2020

Cited by 4 | Viewed by 3279

Abstract

The Reeb graph of a scalar function that is defined on a domain gives a topologically meaningful summary of that domain. Reeb graphs have been shown in the past decade to be of great importance in geometric processing, image processing, computer graphics, and [...] Read more.

The Reeb graph of a scalar function that is defined on a domain gives a topologically meaningful summary of that domain. Reeb graphs have been shown in the past decade to be of great importance in geometric processing, image processing, computer graphics, and computational topology. The demand for analyzing large data sets has increased in the last decade. Hence, the parallelization of topological computations needs to be more fully considered. We propose a parallel augmented Reeb graph algorithm on triangulated meshes with and without a boundary. That is, in addition to our parallel algorithm for computing a Reeb graph, we describe a method for extracting the original manifold data from the Reeb graph structure. We demonstrate the running time of our algorithm on standard datasets. As an application, we show how our algorithm can be utilized in mesh segmentation algorithms. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

19 pages, 2232 KiB

Open AccessArticle

Detecting Traffic Incidents Using Persistence Diagrams

by Eric S. Weber, Steven N. Harding and Lee Przybylski

Algorithms 2020, 13(9), 222; https://0-doi-org.brum.beds.ac.uk/10.3390/a13090222 - 05 Sep 2020

Cited by 3 | Viewed by 2638

Abstract

We introduce a novel methodology for anomaly detection in time-series data. The method uses persistence diagrams and bottleneck distances to identify anomalies. Specifically, we generate multiple predictors by randomly bagging the data (reference bags), then for each data point replacing the data point [...] Read more.

We introduce a novel methodology for anomaly detection in time-series data. The method uses persistence diagrams and bottleneck distances to identify anomalies. Specifically, we generate multiple predictors by randomly bagging the data (reference bags), then for each data point replacing the data point for a randomly chosen point in each bag (modified bags). The predictors then are the set of bottleneck distances for the reference/modified bag pairs. We prove the stability of the predictors as the number of bags increases. We apply our methodology to traffic data and measure the performance for identifying known incidents. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

15 pages, 315 KiB

Open AccessArticle

Adaptive Metrics for Adaptive Samples

by Nicholas J. Cavanna and Donald R. Sheehy

Algorithms 2020, 13(8), 200; https://0-doi-org.brum.beds.ac.uk/10.3390/a13080200 - 18 Aug 2020

Viewed by 2451

Abstract

We generalize the local-feature size definition of adaptive sampling used in surface reconstruction to relate it to an alternative metric on Euclidean space. In the new metric, adaptive samples become uniform samples, making it simpler both to give adaptive sampling versions of homological [...] Read more.

We generalize the local-feature size definition of adaptive sampling used in surface reconstruction to relate it to an alternative metric on Euclidean space. In the new metric, adaptive samples become uniform samples, making it simpler both to give adaptive sampling versions of homological inference results and to prove topological guarantees using the critical points theory of distance functions. This ultimately leads to an algorithm for homology inference from samples whose spacing depends on their distance to a discrete representation of the complement space. Full article

(This article belongs to the Special Issue Topological Data Analysis)

15 pages, 600 KiB

Open AccessArticle

Approximate Triangulations of Grassmann Manifolds

by Kevin P. Knudson

Algorithms 2020, 13(7), 172; https://0-doi-org.brum.beds.ac.uk/10.3390/a13070172 - 17 Jul 2020

Cited by 1 | Viewed by 3055

Abstract

We define the notion of an approximate triangulation for a manifold M embedded in Euclidean space. The basic idea is to build a nested family of simplicial complexes whose vertices lie in M and use persistent homology to find a complex in the [...] Read more.

We define the notion of an approximate triangulation for a manifold M embedded in Euclidean space. The basic idea is to build a nested family of simplicial complexes whose vertices lie in M and use persistent homology to find a complex in the family whose homology agrees with that of M. Our key examples are various Grassmann manifolds

G_{k} (R^{n})

. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

25 pages, 8825 KiB

Open AccessArticle

Fibers of Failure: Classifying Errors in Predictive Processes

by Leo S. Carlsson, Mikael Vejdemo-Johansson, Gunnar Carlsson and Pär G. Jönsson

Algorithms 2020, 13(6), 150; https://0-doi-org.brum.beds.ac.uk/10.3390/a13060150 - 23 Jun 2020

Viewed by 4098

Abstract

Predictive models are used in many different fields of science and engineering and are always prone to make faulty predictions. These faulty predictions can be more or less malignant depending on the model application. We describe fibers of failure (FiFa [...] Read more.

Predictive models are used in many different fields of science and engineering and are always prone to make faulty predictions. These faulty predictions can be more or less malignant depending on the model application. We describe fibers of failure (FiFa), a method to classify failure modes of predictive processes. Our method uses Mapper, an algorithm from topological data analysis (TDA), to build a graphical model of input data stratified by prediction errors. We demonstrate two ways to use the failure mode groupings: either to produce a correction layer that adjusts predictions by similarity to the failure modes; or to inspect members of the failure modes to illustrate and investigate what characterizes each failure mode. We demonstrate FiFa on two scenarios: a convolutional neural network (CNN) predicting MNIST images with added noise, and an artificial neural network (ANN) predicting the electrical energy consumption of an electric arc furnace (EAF). The correction layer on the CNN model improved its prediction accuracy significantly while the inspection of failure modes for the EAF model provided guiding insights into the domain-specific reasons behind several high-error regions. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

13 pages, 2288 KiB

Open AccessArticle

A Distributed Approach to the Evasion Problem

by Denis Khryashchev, Jie Chu, Mikael Vejdemo-Johansson and Ping Ji

Algorithms 2020, 13(6), 149; https://0-doi-org.brum.beds.ac.uk/10.3390/a13060149 - 23 Jun 2020

Viewed by 3208

Abstract

The Evasion Problem is the question of whether—given a collection of sensors and a particular movement pattern over time—it is possible to stay undetected within the domain over the same stretch of time. It has been studied using topological techniques since 2006—with sufficient [...] Read more.

The Evasion Problem is the question of whether—given a collection of sensors and a particular movement pattern over time—it is possible to stay undetected within the domain over the same stretch of time. It has been studied using topological techniques since 2006—with sufficient conditions for non-existence of an Evasion Path provided by de Silva and Ghrist; sufficient and necessary conditions with extended sensor capabilities provided by Adams and Carlsson; and sufficient and necessary conditions using sheaf theory by Krishnan and Ghrist. In this paper, we propose three algorithms for the Evasion Problem: one distributed algorithm extension of Adams’ approach for evasion path detection, and two different approaches to evasion path enumeration. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

18 pages, 495 KiB

Open AccessArticle

Computing Persistent Homology of Directed Flag Complexes

by Daniel Lütgehetmann, Dejan Govc, Jason P. Smith and Ran Levi

Algorithms 2020, 13(1), 19; https://0-doi-org.brum.beds.ac.uk/10.3390/a13010019 - 07 Jan 2020

Cited by 15 | Viewed by 5720

Abstract

We present a new computing package Flagser, designed to construct the directed flag complex of a finite directed graph, and compute persistent homology for flexibly defined filtrations on the graph and the resulting complex. The persistent homology computation part of F [...] Read more.

We present a new computing package Flagser, designed to construct the directed flag complex of a finite directed graph, and compute persistent homology for flexibly defined filtrations on the graph and the resulting complex. The persistent homology computation part of Flagser is based on the program Ripser by U. Bauer, but is optimised specifically for large computations. The construction of the directed flag complex is done in a way that allows easy parallelisation by arbitrarily many cores. Flagser also has the option of working with undirected graphs. For homology computations Flagser has an approximate option, which shortens compute time with remarkable accuracy. We demonstrate the power of Flagser by applying it to the construction of the directed flag complex of digital reconstructions of brain microcircuitry by the Blue Brain Project and several other examples. In some instances we perform computation of homology. For a more complete performance analysis, we also apply Flagser to some other data collections. In all cases the hardware used in the computation, the use of memory and the compute time are recorded. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Figure 1

19 pages, 3958 KiB

Open AccessArticle

A Numerical Approach for the Filtered Generalized Čech Complex

by Jesús F. Espinoza, Rosalía Hernández-Amador, Héctor A. Hernández-Hernández and Beatriz Ramonetti-Valencia

Algorithms 2020, 13(1), 11; https://0-doi-org.brum.beds.ac.uk/10.3390/a13010011 - 30 Dec 2019

Cited by 5 | Viewed by 3616

Abstract

In this paper, we present an algorithm to compute the filtered generalized Čech complex for a finite collection of disks in the plane, which do not necessarily have the same radius. The key step behind the algorithm is to calculate the minimum scale [...] Read more.

In this paper, we present an algorithm to compute the filtered generalized Čech complex for a finite collection of disks in the plane, which do not necessarily have the same radius. The key step behind the algorithm is to calculate the minimum scale factor needed to ensure rescaled disks have a nonempty intersection, through a numerical approach, whose convergence is guaranteed by a generalization of the well-known Vietoris–Rips Lemma, which we also prove in an alternative way, using elementary geometric arguments. We give an algorithm for computing the 2-dimensional filtered generalized Čech complex of a finite collection of d-dimensional disks in

R^{d}

, and we show the performance of our algorithm. Full article

(This article belongs to the Special Issue Topological Data Analysis)

► Show Figures

Graphical abstract

Journal Menu

Journal Browser

Topological Data Analysis

Share This Special Issue

Special Issue Editor

Special Issue Information

Keywords

Published Papers (11 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI