@article{kim_stable_2018,
abstract = {When studying flocking/swarming behaviors in animals one is interested in quantifying and comparing the dynamics of the clustering induced by the coalescence and disbanding of animals in different groups. In a similar vein, studying the dynamics of social networks leads to the problem of characterizing groups/communities as they form and disperse throughout time. Motivated by this, we study the problem of obtaining persistent homology based summaries of time-dependent data. Given a finite dynamic graph ({DG}), we first construct a zigzag persistence module arising from linearizing the dynamic transitive graph naturally induced from the input {DG}. Based on standard results, we then obtain a persistence diagram or barcode from this zigzag persistence module. We prove that these barcodes are stable under perturbations in the input {DG} under a suitable distance between {DGs} that we identify. More precisely, our stability theorem can be interpreted as providing a lower bound for the distance between {DGs}. Since it relies on barcodes, and their bottleneck distance, this lower bound can be computed in polynomial time from the {DG} inputs. Since {DGs} can be given rise by applying the Rips functor (with a fixed threshold) to dynamic metric spaces, we are also able to derive related stable invariants for these richer class of dynamic objects. Along the way, we propose a summarization of dynamic graphs that captures their time-dependent clustering features which we call formigrams. These set-valued functions generalize the notion of dendrogram, a prevalent tool for hierarchical clustering. In order to elucidate the relationship between our distance between two {DGs} and the bottleneck distance between their associated barcodes, we exploit recent advances in the stability of zigzag persistence due to Botnan and Lesnick, and to Bjerkevik.},
author = {Kim, Woojin and Memoli, Facundo},
date = {2018-08-03},
eprint = {1712.04064},
eprinttype = {arxiv},
journaltitle = {{arXiv}:1712.04064 [cs, math]},
keywords = {1 - Animal behavior, 1 - Dynamic graphs, 1 - Dynamical systems, 1 - Social network, 2 - Persistent homology, 2 - Zigzag, 3 - Animal behavior, 3 - Time-varying data, 3 - graphs:directed},
title = {Stable signatures for dynamic graphs and dynamic metric spaces via zigzag persistence},
url = {http://arxiv.org/abs/1712.04064},
urldate = {2020-01-04}
}