Dynamic FastMap: An Efficient Algorithm for Spatiotemporal Embedding of Dynamic Graphs

Abstract

Efficiently embedding graphs in a Euclidean space has many benefits: It allows us to interpret and solve graph-theoretic problems using geometric and analytical methods. It also allows us to visualize graphs and support human-in-the-loop decision-making systems. FastMap is a near-linear-time graph embedding algorithm that has already found many real-world applications. In this paper, we generalize FastMap to Dynamic FastMap, which efficiently embeds dynamic graphs, i.e., graphs with time-dependent edge-weights, in a spatiotemporal space with a user-specified number of dimensions, while reserving one dimension for representing time. Through a range of experiments, we also demonstrate the efficacy of Dynamic FastMap as an algorithm for spatiotemporal embedding of dynamic graphs.