An embedding-based distance for temporal graphs
arXiv:2401.12843 · doi:10.1038/s41467-024-54280-4
Abstract
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.
References in corpus (12)
- Stochastic blockmodels and community structure in networks
- Dynamics of person-to-person interactions from distributed RFID sensor networks
- What's in a crowd? Analysis of face-to-face behavioral networks
- Path lengths, correlations, and centrality in temporal networks
- Contact patterns among high school students
- Mitigation of infectious disease at school: targeted class closure vs school closure
- An infectious disease model on empirical networks of human contact: bridging the gap between dynamic network data and contact matrices
- Network comparison and the within-ensemble graph distance
- Detecting social (in)stability in primates from their temporal co-presence network
- Gender and collaboration patterns in a temporal scientific authorship network
- Flow of temporal network properties under local aggregation and time shuffling: a tool for characterizing, comparing and classifying temporal networks
- Measuring and utilizing temporal network dissimilarity