Time-Constrained Graph Pattern Matching In A Large Temporal Graph

Graph pattern matching(GPM)is an important operation on graph computation and plays a significant role in many fields,such as information retrieval,community detecting and biology.The development of GPM undergoes three periods.(1)Firstly,a lot of researchers investigate the problem of querying static graph pattern in static graphs.However,graphs in real life are inherently dynamic.(2)Therefore,a lot of efforts have been made in querying static graph pattern in dynamic graphs.(3)Recently,to discover more interesting patterns,there exists a few work about querying dynamic graph pattern in dynamic graphs.However,there exist following issues in traditional work:(1)The dynamic graph is often modeled as a series of static snapshots.However,a series of snapshots cannot illustrate all temporal information and a part of information is missing.(2)The traditional solutions often offer users a large number of matched subgraphs.It is daunting for users to inspect all matched subgraphs and find what they really want.In this paper,we focus on studying temporal graphs which can show more information than a series of snapshots.Besides,we design two types of time constraints in the query graph to reduce the number of matched subgraphs.In this paper,we propose a new problem,i.e.,time-constrained graph pattern matching in a large temporal graph.To solve this problem,we propose two solutions.(1)TCGPM-V(Time-Constrained Graph Pattern Matching based on Vertex Mapping).This solution contains four steps: mapping vertex,constructing graph,enumerating temporal graphs and verifying temporal graphs.(2)To improve the efficiency,we propose TCGPM-E(Time-Constrained Graph Pattern Matching based on Edge Mapping).This solution contains six steps: selecting center edge,computing radius,computing a set of edges,decomposing data graph,mapping edge,enumerating and verifying temporal graphs.To evaluate the effectiveness and efficiency of proposed solutions,extensive experiments are conducted on real datasets,such as Contact,Social Pattern,SEQ and Patents.Besides,we compare proposed solutions with Ullman,VF2 and Graph QL.The results demonstrate the good performance of proposed solutions.