Navigation on Temporal Networks

Abstract Temporal networks, whose network topology changes over time, are used to represent, e.g., opportunistic mobile networks, vehicle networks, and social contact networks, where two mobile devices (autos or individuals) are connected only when they are close to (interact with) each other. Such networks facilitate the transfer of information. In this paper, we address the problem of navigation on temporal networks: how to route a traffic demand from a source s to a destination d at time ts, based on the network observed before ts? Whenever the node hosting the information has a contact or interacts with another node, the routing method has to decide whether the information should be forwarded to the contacted node or not. Once the information is forwarded, the contacted node becomes the only node hosting the information. Firstly, we introduce a framework of designing navigation algorithms, in which a distance metric is defined and computed between any node to the target d based on the network observed before ts. Whenever a hosting node has a contact, it forwards the information to the contacted node if the contacted node is closer to the target than the hosting node according to the distance metric. Secondly, we propose systematically distance metrics of a node pair in the temporal network observed, that capture different network properties of a node pair. Thirdly, these metrics or routing strategies are evaluated in empirical contact networks, from the perspective of the time duration of the routing and the probability that the destination can be reached. Their performance is further explained via the correlation between distance metrics and the stability of each metric in ranking nodes' distance to a target node. These contributions are deemed as the first step towards navigation on realistic mobile, vehicle or social networks.