Evolution Forest Index: Towards Optimal Temporal $k$-Core Component Search via Time-Topology Isomorphic Computation

Download PDF

Abstract

For a temporal graph like transaction network, finding a densely connected subgraph that contains a vertex like a suspicious account during a period is valuable. Thus, we study the Temporal 𝑘-Core Component Search (TCCS) problem, which aims to find a connected component of temporal 𝑘-core for any given vertex and time interval. Towards this goal, we propose a novel Evolution Forest Index (EF-Index) that can address TCCS in optimal time. Essentially, EFIndex leverages the evolutionary order on temporal 𝑘-cores to both compress the connectivity between vertices in temporal 𝑘-cores of all time intervals into a minimum set of compactest Minimum Temporal Spanning Forests (MTSFs) and retrieve MTSF for a given time interval rapidly. Here, a crucial innovation is that, we extend the temporal 𝑘-core evolution theory by introducing a pair of time-topology isomorphic relations, on top of which the evolutionary order in topology domain can be simply computed by a “kernel function” in time domain. Moreover, we design an efficient mechanism to update EF-Index incrementally for dynamic edge streams. The experimental results on a variety of real-world temporal graphs demonstrate that, EF-Index outperforms the state-of-the-art approach by 1-3 orders of magnitude on processing TCCS, and its space overhead is reduced by 4-5 orders of magnitude compared with preserving connectivity uncompressedly.