Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology
Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology
复制标题
使用持久同源性视觉检测时变图中的结构变化
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Rosen
中科院分区：
文献类型：
--
作者：
Mustafa Hajij;Bei Wang;C. Scheidegger;P. Rosen
拓扑数据分析是探索性数据分析和数据挖掘中的一个新兴领域。它的主要工具——持久同调，已经成为研究复杂、高维数据结构的一种流行技术。本文提出了一种利用持续同调来量化时变图结构变化的新方法。具体来说，我们将时变图的每个实例转换为度量空间，使用持久同调提取拓扑特征，并随时间比较这些特征。我们提供了一种可视化的方法，可以帮助进行时变图形的探索，并帮助识别数据中的行为模式。为了验证我们的方法，我们对现实世界的数据集进行了几个案例研究，并展示了我们的方法如何在时变图中发现循环模式、偏离这些模式和一次性事件。我们还研究了基于持久性的相似性度量是否满足一组完善的、理想的图度量属性。
Topological data analysis is an emerging area in exploratory data analysis and data mining. Its main tool, persistent homology, has become a popular technique to study the structure of complex, high-dimensional data. In this paper, we propose a novel method using persistent homology to quantify structural changes in time-varying graphs. Specifically, we transform each instance of the time-varying graph into a metric space, extract topological features using persistent homology, and compare those features over time. We provide a visualization that assists in time-varying graph exploration and helps to identify patterns of behavior within the data. To validate our approach, we conduct several case studies on real-world datasets and show how our method can find cyclic patterns, deviations from those patterns, and one-time events in time-varying graphs. We also examine whether a persistence-based similarity measure satisfies a set of well-established, desirable properties for graph metrics.