Dall'Amico Lorenzo, Barrat Alain, Cattuto Ciro
ISI Foundation, Turin, 10126, Italy.
Aix-Marseille Univ, Université de Toulon, CNRS, CPT, Marseille, 13009, France.
Nat Commun. 2024 Nov 17;15(1):9954. doi: 10.1038/s41467-024-54280-4.
Temporal graphs are commonly used to represent time-resolved relations between entities in many natural and artificial systems. Many techniques were devised to investigate the evolution of temporal graphs by comparing their state at different time points. However, quantifying the similarity between temporal graphs as a whole is an open problem. Here, we use embeddings based on time-respecting random walks to introduce a new notion of distance between temporal graphs. This distance is well-defined for pairs of temporal graphs with different numbers of nodes and different time spans. We study the case of a matched pair of graphs, when a known relation exists between their nodes, and the case of unmatched graphs, when such a relation is unavailable and the graphs may be of different sizes. We use empirical and synthetic temporal network data to show that the distance we introduce discriminates graphs with different topological and temporal properties. We provide an efficient implementation of the distance computation suitable for large-scale temporal graphs.
时态图通常用于表示许多自然和人工系统中实体之间的时间分辨关系。人们设计了许多技术，通过比较时态图在不同时间点的状态来研究其演化。然而，量化时态图作为一个整体之间的相似性是一个悬而未决的问题。在这里，我们使用基于尊重时间的随机游走的嵌入来引入时态图之间距离的新概念。对于具有不同节点数和不同时间跨度的时态图对，这种距离是明确定义的。我们研究了一对匹配图的情况，即它们的节点之间存在已知关系，以及不匹配图的情况，即不存在这种关系且图的大小可能不同。我们使用经验性和合成的时态网络数据来表明，我们引入的距离能够区分具有不同拓扑和时间属性的图。我们提供了一种适用于大规模时态图的距离计算的高效实现。
