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 k -Core Component Search (TCCS) problem, which aims to find a connected component of temporal k -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, EF-Index leverages the evolutionary order on temporal k -cores to both compress the connectivity between vertices in temporal k -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 k -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.

Querying cohesive subgraphs on temporal graphs (e.g., social network, finance network, etc.) with various conditions has attracted intensive research interests recently. In this paper, we study a novel Temporal$(k,\mathcal {X})$-Core Query (TXCQ) that extends a fundamental Temporal$k$-Core Query (TCQ) proposed in our conference paper by optimizing or constraining an arbitrary metric$\mathcal {X}$of$k$-core, such as size, engagement, interaction frequency, time span, burstiness, periodicity, etc. Our objective is to address specific TXCQ instances with conditions on different$\mathcal {X}$in a unified algorithm framework that guarantees scalability. For that, this journal paper proposes a taxonomy of measurement$\mathcal {X}(\cdot )$and achieve our objective using a two-phase framework while$\mathcal {X}(\cdot )$is time-insensitive or time-monotonic. Specifically, Phase 1 still leverages the query processing algorithm of TCQ to induce all distinct$k$-cores during a given time range, and meanwhile locates the “time zones” in which the cores emerge. Then, Phase 2 conducts fast local search and$\mathcal {X}$evaluation in each time zone with respect to the time insensitivity or monotonicity of$\mathcal {X}(\cdot )$. By revealing two insightful concepts named tightest time interval and loosest time interval that bound time zones, the redundant core induction and unnecessary$\mathcal {X}$evaluation in a zone can be reduced dramatically. Our experimental results demonstrate that TXCQ can be addressed as efficiently as TCQ, which achieves the latest state-of-the-art performance, by using a general algorithm framework that leaves$\mathcal {X}(\cdot )$as a user-defined function.

Querying cohesive subgraphs on temporal graphs with various time constraints has attracted intensive research interests recently. In this paper, we study a novel Temporal k -Core Query (TCQ) problem: given a time interval, find all distinct k -cores that exist within any subintervals from a temporal graph, which generalizes the previous historical k -core query. This problem is challenging because the number of subintervals increases quadratically to the span of time interval. For that, we propose a novel Temporal Core Decomposition (TCD) algorithm that decrementally induces temporal k -cores from the previously induced ones and thus reduces "intra-core" redundant computation significantly. Then, we introduce an intuitive concept named Tightest Time Interval (TTI) for temporal k -core, and design an optimization technique with theoretical guarantee that leverages TTI as a key to predict which subintervals will induce duplicated k -cores and prunes the subintervals completely in advance, thereby eliminating "inter-core" redundant computation. The complexity of optimized TCD (OTCD) algorithm no longer depends on the span of query time interval but only the scale of final results, which means OTCD algorithm is scalable. Moreover, we propose a compact in-memory data structure named Temporal Edge List (TEL) to implement OTCD algorithm efficiently in physical level with bounded memory requirement. TEL organizes temporal edges in a "timeline" and can be updated instantly when new edges arrive in dynamical temporal graphs. We compare OTCD algorithm with the incremental historical k -core query on several real-world temporal graphs, and observe that OTCD algorithm outperforms it by three orders of magnitude, even though OTCD algorithm needs none precomputed index.