Multi-Constrained Path And K-Closest-Pairs Query In Temporal Graphs

Many applications in real life can be abstracted into problems in the graph,such as disease progress tracking in the genetic network,which can be abstracted into the path query problem in the graph;Urban planning can be abstracted into k-closest-pairs query problem in the graph;Analysis and comparison of protein interaction networks can be abstracted into graph matching problem and so on.The paper mainly focuses on the first two problems,namely,path query and k-closest-pairs query in graphs.In the existing path query and k-closest-pairs query work,there are two main problems:(1)Most of the existing research is based on static graphs,and some studies involve path problems on dynamic graphs,but there is currently no related research on k-closest-pairs on dynamic graphs;(2)Existing research does not consider that there might be attribute information on the edge of the graph,nor does it consider that the user might have specific requirements for time interval and attributes on the edge when executing the query.To address the problems aforementioned,we propose a model to describe the real-life network in an appropriate way,and also propose a query method to better meet the users'query needs.The main contributions of this paper are as follows:(1)The concept of attributed temporal graph is proposed,based on attributed tempo-ral graph,the multi-constrained earliest arrival path,multi-constrained latest departure path problem and multi-constrained k-closest-pairs query problem are proposed;(2)A set of approximation algorithms,called two-scan algorithm,is proposed.In the first step,an objective function is proposed,which consists of multiple constraints and at-tributes values,indicating whether the temporal path is feasible.In the second step,the algorithm searches the temporal graph to find the temporal path that satisfies the constraints;(3)Combined with the divide-and-conquer method,a grid decomposition method is proposed to accelerate the query of k-closest-pairs in the temporal graph.In addition,the algorithm to answer multi-constrained shortest path between any two vertices is a modified version of the proposed two-scan algorithm;(4)This paper evaluates the proposed methods on multiple real data sets such as Enron,Openflights,and Arxiv,and compares them with the latest existing methods.The experi-mental results show that the efficiency and effectiveness are better than existing methods.