关键词: 时序图, 持续性稠密子图, 高效搜索算法

Abstract: Temporal graph is a kind of graph structure with timestamps on its edges, where the timestamps indicate the time when the edges appear, that is, the graph evolves constantly by time. The problem of cohesive subgraph mining for graph data has very strong practical significance. Recently, most of the existing work in temporal graphs focus on the problem of cohesive subgraph detection, which aims to find all the target subgraphs in the temporal graph. However, when the size of the temporal graph becoming too large, the problem of cohesive subgraph detection will go extremely impractical and ineffective. The purpose of this paper is to study the problem of cohesive subgraph search, which has been overlooked for long. Specifically, given a query vertex in the temporal graph, the goal is to find a cohesive subgraph that sustaining over a period and include the query vertex. That is the subgraph satisfies the time sustainability. To this end, two efficient searching algorithms are designed based on global reduction and local expansion to cope with different application scenarios. A large number of experiments on four real networks verify the efficiency of the proposed algorithms.

Key words: temporal graph, sustained cohesive subgraph, efficient searching algorithm