Stable Signatures for Dynamic Graphs and Dynamic Metric Spaces via Zigzag Persistence
Stable Signatures for Dynamic Graphs and Dynamic Metric Spaces via Zigzag Persistence
复制标题
通过 Zigzag 持久性实现动态图和动态度量空间的稳定签名
DOI：
10.31235/osf.io/9mbdn
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
F. Mémoli
中科院分区：
文献类型：
--
作者：
Woojin Kim;F. Mémoli
当研究动物的群集/群集行为时，人们感兴趣的是量化和比较由不同群体中动物的合并和解散引起的集群动态。同样，研究社交网络的动态也会导致如何在群体/社区形成和分散的过程中确定其特征的问题。
出于这一动机，我们研究的问题，获得持久的同源性为基础的总结时间依赖性的数据。给定一个有限动态图，我们首先构造一个锯齿形持久化模块，该模块是通过线性化从输入动态图自然导出的动态传递图而产生的。基于标准结果，我们从这个锯齿形持久化模块中获得持久化图或条形码。我们证明，这些条形码是稳定的扰动下，在输入DG之间的DG，我们确定一个合适的距离。
更准确地说，我们的稳定性定理可以解释为提供了一个下界的DG之间的距离。由于它依赖于条形码和它们的瓶颈距离，因此可以从DG输入在多项式时间内计算该下限。
由于DG可以通过将RIP函子（具有固定阈值）应用于动态度量空间来产生，因此我们也能够为这些更丰富的动态对象类导出相关的稳定不变量。
沿着的方式，我们提出了一个动态图，捕捉他们的时间相关的聚类功能，我们称之为formigrams的总结。这些集值函数推广了树状图的概念，树状图是一种流行的分层聚类工具。为了阐明两个DG之间的距离与其相关条形码之间的瓶颈距离之间的关系，我们利用Botnan和Lesnick以及Bjerkevik在锯齿形持久性稳定性方面的最新进展。
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.