Dey, Tamal K. ;
Hou, Tao
Computing Zigzag Persistence on Graphs in NearLinear Time
Abstract
Graphs model realworld circumstances in many applications where they may constantly change to capture the dynamic behavior of the phenomena. Topological persistence which provides a set of birth and death pairs for the topological features is one instrument for analyzing such changing graph data. However, standard persistent homology defined over a growing space cannot always capture such a dynamic process unless shrinking with deletions is also allowed. Hence, zigzag persistence which incorporates both insertions and deletions of simplices is more appropriate in such a setting. Unlike standard persistence which admits nearly lineartime algorithms for graphs, such results for the zigzag version improving the general O(m^ω) time complexity are not known, where ω < 2.37286 is the matrix multiplication exponent. In this paper, we propose algorithms for zigzag persistence on graphs which run in nearlinear time. Specifically, given a filtration with m additions and deletions on a graph with n vertices and edges, the algorithm for 0dimension runs in O(mlog² n+mlog m) time and the algorithm for 1dimension runs in O(mlog⁴ n) time. The algorithm for 0dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2manifolds. The algorithm for 1dimension pairs a negative edge with the earliest positive edge so that a 1cycle containing both edges resides in all intermediate graphs. Both algorithms achieve the claimed time complexity via dynamic graph data structures proposed by Holm et al. In the end, using Alexander duality, we extend the algorithm for 0dimension to compute the (p1)dimensional zigzag persistence for ℝ^pembedded complexes in O(mlog² n+mlog m+nlog n) time.
BibTeX  Entry
@InProceedings{dey_et_al:LIPIcs.SoCG.2021.30,
author = {Dey, Tamal K. and Hou, Tao},
title = {{Computing Zigzag Persistence on Graphs in NearLinear Time}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {30:130:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771849},
ISSN = {18688969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13829},
URN = {urn:nbn:de:0030drops138292},
doi = {10.4230/LIPIcs.SoCG.2021.30},
annote = {Keywords: persistent homology, zigzag persistence, graph filtration, dynamic networks}
}
02.06.2021
Keywords: 

persistent homology, zigzag persistence, graph filtration, dynamic networks 
Seminar: 

37th International Symposium on Computational Geometry (SoCG 2021)

Issue date: 

2021 
Date of publication: 

02.06.2021 