Title: Stable Signatures for Dynamic Graphs and Dynamic Metric Spaces via Zigzag Persistence,
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.