期刊
KNOWLEDGE-BASED SYSTEMS
卷 278, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.knosys.2023.110855
关键词
Persistent homology; Dynamic graph analysis; Graph comparison; Topological data analysis
Persistent homology theory is widely used for analyzing topological features, but existing methods are not suitable for the time-varying structure in dynamic graphs. This paper proposes Stable Distance of Persistent Homology (SDPH) to compare and quantify the differences in the topological properties of dynamic graphs. The proposed approach, utilizing Dynamic Dowker Filtration and Time-interlevel Kernel, effectively measures the topological difference of dynamic graphs.
Persistent homology theory provides approaches for analyzing topological features, which is now widely applied in graph comparison on social networks, biological networks, and co-location networks. These approaches utilize filtration techniques to extract the topological properties of a graph and construct vectorizations that represent these properties for further computation. However, most existing methods are designed for static scenarios and are unsuitable for the time-varying structure in realistic dynamic graphs. In this paper, we propose the Stable Distance of Persistent Homology (SDPH) to compare and quantify the differences in the topological properties of dynamic graphs. In detail, we design Dynamic Dowker Filtration (DDF) to map dynamic graph to a persistent complex based on the e-interleaved theory, which enables us to trace the structure holes formed by the accumulation of temporal edge via computing the persistent homology. DDF exhibits stability and duality, inducing a time-structure triangle inequality. Based on this inequality, we finally construct Time-interlevel Kernel (TIK) for vectorizing the extracted topological features with an inner product. We conduct the graph clustering and classification experiments on synthetic and real-world datasets. Experimental results show that the proposed SDPH outperforms the baseline methods in these tasks and validate that the proposed SDPH can effectively measure the topological difference of dynamic graphs. Through SDPH, we would provide insight and inspiration on how to apply persistent homology theory to dynamic graph analysis. (c) 2023 Published by Elsevier B.V.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据