Search Results

Documents authored by Li, Tianqi


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

Authors: Tamal K. Dey, Tianqi Li, and Yusu Wang

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


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.

Cite as

Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2020.36,
  author =	{Dey, Tamal K. and Li, Tianqi and Wang, Yusu},
  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 =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.36},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail