The Walk-Length Filtration for Persistent Homology on Weighted Directed Graphs
This work offers a novel method for extracting topological features from directed graphs, which is important for applications in network analysis, but the improvements are incremental compared to existing methods.
The paper introduces a new filtration for persistent homology on weighted directed graphs, called the walk-length filtration, which is stable under a generalized L1-style distance. It provides an algorithm for computation and demonstrates its behavior on examples, showing advantages over the Dowker filtration.
Directed graphs arise in many applications where computing persistent homology helps to encode the shape and structure of the input information. However, there are only a few ways to turn the directed graph information into an undirected simplicial complex filtration required by the standard persistent homology framework. In this paper, we present a new filtration constructed from a directed graph, called the walk-length filtration. This filtration mirrors the behavior of small walks visiting certain collections of vertices in the directed graph. We show that, while the persistence is not stable under the usual $L_\infty$-style network distance, a generalized $L_1$-style distance is, indeed, stable. We further provide an algorithm for its computation, and investigate the behavior of this filtration in examples, including cycle networks and synthetic hippocampal networks with a focus on comparison to the often used Dowker filtration.