RECORD
Scalable Time-Range k-Core Query on Temporal Graphs(Full Version)
Databases · Submitted 10 Jan 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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, and thus our approach can also deal with dynamic 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Querying cohesive subgraphs on temporal graphs with various time constraints has attracted intensive research interests recently. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | 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. | contribution 0.93 | 0.71 | 0.07 | asserted 0.98 |
| s2 | This problem is challenging because the number of subintervals increases quadratically to the span of time interval. | background 0.71 | 0.18 | 0.02 | asserted 1.00 |
| s3 | 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. | method 0.70 | 0.94 | 0.07 | asserted 1.00 |
| s4 | 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. | method 0.61 | 0.95 | 0.10 | asserted 1.00 |
| s5 | 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. | interpretation 0.52 | 0.90 | 0.47 | asserted 1.00 |
| s6 | 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. | method 0.68 | 0.94 | 0.05 | asserted 1.00 |
| s7 | TEL organizes temporal edges in a "timeline" and can be updated instantly when new edges arrive, and thus our approach can also deal with dynamic temporal graphs. | method 0.56 | 0.90 | 0.04 | asserted 0.98 |
| s8 | 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. | result 1.00 | 0.97 | 0.47 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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, and thus our approach can also deal with dynamic 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.
Human review
How the literature uses it
2 arXiv papers cite this in 5 sentences
Papers citing it · 1 sentence without a confident label
Builds on it 1 paper
-
Similarly, [ref] extend the work of [ref] and introduce time-range k-cores queries by allowing the resulting $k$-cores to be induced by any subinterval $I'⊆I$ of the time interval $I$.
An Edge-Based Decomposition Framework for Temporal Networks · Related Work · 0.90
Compares with it 1 paper
-
Interval queries: The approaches that query a static $k$-core during an interval [ref] can, e.g., identify the $(3,5)$-core shown in <Ref> by carefully choosing the interval $[1,8]$.
An Edge-Based Decomposition Framework for Temporal Networks · Comparison of Decompositions · 0.99
Cites it as background 2 papers
-
For the temporal networks in the time interval $[t_s,t_e]$, we have $𝒢 = (𝒩,ℰ,ℒ)$ [ref] , where:
Critical Node Detection in Temporal Social Networks, Based on Global and Semi-local Centrality Measures · Temporal networks · 0.91
-
The works of [ref] focus on efficiently answering queries for the standard $k$-core definition in given time intervals, and the authors introduce indexing techniques to answer such queries efficiently.
An Edge-Based Decomposition Framework for Temporal Networks · Related Work · 0.92
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.