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 (35)
- Emergence of scaling in random networks
- The structure and function of complex networks
- T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction
- Classes of behavior of small-world networks
- Temporal Networks
- Spatial Networks
- Stochastic blockmodels and community structure in networks
- Graph Embedding Techniques, Applications, and Performance: A Survey
- High-resolution measurements of face-to-face contact patterns in a primary school
- Dynamics of person-to-person interactions from distributed RFID sensor networks
- What's in a crowd? Analysis of face-to-face behavioral networks
- High resolution dynamical mapping of social interactions with active RFID
- Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
- Random Geometric Graphs
- Community Discovery in Dynamic Networks: a Survey
- Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors
- Measuring large-scale social networks with high resolution
- Path lengths, correlations, and centrality in temporal networks
- Contact patterns among high school students
- Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
- Can co-location be used as a proxy for face-to-face contacts?
- Mitigation of infectious disease at school: targeted class closure vs school closure
- NetLSD: Hearing the Shape of a Graph
- Adaptive Evolutionary Clustering
- An infectious disease model on empirical networks of human contact: bridging the gap between dynamic network data and contact matrices
- An information-theoretic, all-scales approach to comparing networks
- Detecting sequences of system states in temporal networks
- Randomized reference models for temporal networks
- Network comparison and the within-ensemble graph distance
- Detecting social (in)stability in primates from their temporal co-presence network
- Exploring Temporal Networks with Greedy Walks
- Gender and collaboration patterns in a temporal scientific authorship network
- Comparing Temporal Graphs Using Dynamic Time Warping
- 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