License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.36
URN: urn:nbn:de:0030-drops-121944
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12194/
Go to the corresponding LIPIcs Volume Portal

Dey, Tamal K. ; Li, Tianqi ; Wang, Yusu

An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology

pdf-format:
LIPIcs-SoCG-2020-36.pdf (0.8 MB)

Abstract

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 Grigoryan, 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₁) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the 1-dimensional path-homology. We implement our algorithm and present some preliminary experimental results.

BibTeX - Entry

@InProceedings{dey_et_al:LIPIcs:2020:12194,
  author =	{Tamal K. Dey and Tianqi Li and Yusu Wang},
  title =	{{An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12194},
  URN =		{urn:nbn:de:0030-drops-121944},
  doi =		{10.4230/LIPIcs.SoCG.2020.36},
  annote =	{Keywords: computational topology, directed graph, path homology, persistent path homology}
}

Keywords: computational topology, directed graph, path homology, persistent path homology
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI