Answering Structural And Temporal Reachability Queries On Temporal Graph

In recent years,the rapid development of the Internet has led to a rapid increase in the amount of data.Data from different industries are intertwined by individuals or companies to create a huge data network,such as social networks,information exchange between aircraft routes and biotechnology,etc.Ignoring unnecessary factors,these common application interaction scenarios can be abstracted into the data structure: graph.According to the temporal properties of the graph,problems for reachability query in the graph are divided into two directions.One is about static graph reachability query,in recent decades,the research mainly focuses on static graphs;the other is about temporal graph reachability queries,in this respect,related research has just started.The research of temporal graph for reachability query proposes a solution to the problem of reachability query in a temporal graph.This research decomposes the problem for reachability query into two directions in a temporal graph: one is the structural reachability query,the time attribute of the temporal graph is ignored,and the reachability query is mainly concerned;the other is the temporal state,and the problem of reachability query may focus on the four basic paths of the temporal graph,namely the earliest-arrival path,the latest-departure path,the shortest path and the fastest path.On the issue of structural reachability query,the research on the reachability of temporal graphs analyzes the shortcomings of existing research,and proposes the optimization scheme based on the existing algorithms.On the issue of temporal reachability,an optimal tree model is proposed.Based on the model on this research,an algorithm for solving the four basic paths of the temporal graph is called OPTree.First,in a specific time interval,the algorithm transforms the temporal graph into an optimal tree.Then,the algorithm traverses the optimal tree according to different paths.Finally,it answers reachability queries in the temporality.On the problem of structural reachability query,through the test of 14 real datasets,the optimization scheme proposed by reachability query in a temporal graph is more efficient than the original algorithm;on the problem of temporal reachability query,The correlation algorithm given by this paper can answer the temporal reachability faster than the related algorithms.