Temporal Distances and Cops and Robber Games on Temporal Networks

Abstract

Temporal networks have gained in popularity in the last decade for their ability to model how connections vary over time. We are interested in understanding their structure and analyzing real-world data emerging from temporal networks. We approach those objectives by looking at the Cops and Robber Game from graph theory that is studied for its connection with the structure of graphs as well as by devising algorithms to compute metrics on temporal networks.

Cops and Robber Games have been first extended to the context of temporal networks by Erlebach and Spooner with algorithmic methods. The authors assumed a specific type of schedule that is periodic. We further the study of said games in the context of periodic temporal networks with algorithmic and analytical tools. Thus, we present characterizations of all periodic temporal networks on which a single cop can win, also called copwin. We suggest a structural characterization of copwin periodic graphs. Then, we venture on to explore periodic temporal networks that are not copwin. We also research lower and upper bounds on the number of cops required to capture the robber, i.e. the cop number. This then initiates a classification of periodic temporal networks into classes defined by their properties and their cop numbers.

Moreover, we present algorithms to study some connectivity properties of link streams, a model of temporal networks. These algorithms compute different types of distances on link streams, defined as the minimal number of hops between two temporal nodes, the minimal duration of a temporal path and a combination of both. Those distance functions are relevant for analyzing real-world data and, in particular, to compute an extension of the betweenness centrality on link streams.