Shortest temporal path prediction queries at future time instances

What is it about?

Our work is focused on the prediction of the output of graph queries at a future time instance, we define such queries as future-time graph queries. In this paper we examine the problem of the prediction of temporal paths at a future time instance, given a temporal graph. To process future-time graph queries, we propose an incremental query processing approach that leverages a prediction model that provides oracles about the future state of the graph. Initially, we process the query up to the current time instance. Then, we invoke the oracle to extend processing at future time points. We consider prediction models that provide two types of oracles: (a) a link prediction oracle, and (b) a connection prediction oracle.

Featured Image

Photo by Shubham's Web3 on Unsplash

Photo by Shubham's Web3 on Unsplash

Why is it important?

Graphs are ubiquitous data structures for modeling entities and the relationships between them. For example, in social networks, nodes correspond to people and edges to interactions, or relations between them. Most research on temporal networks focuses on processing queries on the current state of a graph or on the past states of dynamic graphs. Very little research has focused on prediction queries on temporal graphs, where each edge is annotated with information about the time that the corresponding interaction, relationship, communication, transportation or cooperation appeared. The computation of the distance between nodes can be utilized to solve a vast array of complex problems such as clustering. Our algorithms can be used as building blocks for the predictions of the results of such queries at future time points. This research provides a first step to address the problem of the prediction of the shortest temporal path between two nodes at a future time instance.