Approximating the Temporal Neighbourhood Function of Large Temporal Graphs

By

Pierluigi Crescenzi, Clémence Magnien and Andrea Marino

Algorithms 2019, 12(10), 211 (Special Issue Algorithm Engineering: Towards Practically Efficient Solutions to Combinatorial Problems)

Abstract

Temporal networks are graphs in which edges have temporal labels, specifying their
starting times and their traversal times. Several notions of distances between two nodes in a temporal
network can be analyzed, by referring, for example, to the earliest arrival time or to the latest starting
time of a temporal path connecting the two nodes. In this paper we mostly refer to the notion of
temporal reachability by using the earliest arrival time. In particular, we first show how the sketch
approach, which has been already used in the case of classical graphs, can be applied to the case of
temporal networks in order to approximately compute the sizes of the temporal cones of a temporal
network. By making use of this approach, we subsequently show how we can approximate the
temporal neighborhood function (that is, the number of pairs of nodes reachable from one another in
a given time interval) of large temporal networks in a few seconds. Finally, we apply our algorithm
in order to analyze and compare the behavior of 25 public transportation temporal networks. Our
results can be easily adapted to the case in which we want to refer to the notion of distance based on
the latest starting time.

This entry was posted in Papers