Search

Temporal graphs are graphs whose edges are associated with timestamps. Subgraph matching on temporal graphs retrieves temporal subgraphs whose edge timestamps satisfy user-specified temporal orders. In this paper, a temporal query pattern is composed of a query graph with an arbitrary structure and a partial order on the edge set of the query graph. Moreover, the time span between the minimum and the maximum edge timestamps in a matching is required to be less than or equal to a specified threshold. This paper proposes a temporal subgraph matching algorithm based on two key techniques. First, a memory-efficient index structure called TO-tree is designed to compactly store all necessary information required for finding all temporal subgraph matchings. The TO-tree constructed for a temporal query pattern is much smaller than the temporal graph because unnecessary information is mostly excluded from the TO-tree by three powerful filters. The second technique is a temporal subgraph matching enumeration method that runs on the TO-tree instead of on the temporal graph. This enumeration method expands temporal subgraph matchings in an edge-by-edge manner. Since the TO-tree can fit into the main memory, the enumeration method runs very fast on the TO-tree. An extensive experimental evaluation has been carried out. The experimental results show that the TO-tree index structure is memory-efficient, which in turn enables a fast temporal subgraph matching enumeration. Overall, our algorithm is at least 3X faster than the baseline algorithm adapted from the state-of-the-art non-temporal subgraph matching algorithm CECI and is at least 4X faster than the temporal subgraph matching algorithm HASSE .

When characterizing the cohesion of a subgraph, many cohesive subgraph models impose various constraints on the relationship between the minimum degree of vertices and the number of vertices in the subgraph. However, the constraints imposed by the clique, quasi-clique and k-core models are so rigid that they cannot simultaneously characterize cohesive subgraphs of various scales in a graph. This paper characterizes the flexibility of a cohesive subgraph model by the constraint it imposes on this relationship and proposes f -constraint core (f -CC), a new model that can flexibly characterize cohesive subgraphs of different scales. We formalize the FlexCS problem that finds r representative f -CCs in a graph that are most diversified. This problem is NP-hard and is even NP-hard to be approximated within |V |1−𝜖 for any 𝜖 > 0. To solve the problem efficiently, a divide-and-conquer algorithm is proposed together with some effective techniques including f -CC generation, sub-problem filtering, early termination, and index-based connected component retrieval. Extensive experiments verify the flexibility of the f -CC model and the effectiveness of the proposed algorithm.