Temporal k-Cores: A Short Tutorial

Introduction

A temporal graph is a graph in which an edge is not simply present or absent: it is present at a time, or during a time interval. An email, phone call, retweet, contact, trade, or collaboration event is naturally modeled as an edge with a timestamp.

Static graph analysis often aggregates all events into one graph and then runs familiar tools such as degree, connected components, k-core decomposition, or truss decomposition. Aggregation is useful, but it discards ordering and temporal locality. Two users may look highly connected after six months of aggregation even if their interactions never overlap in time.

For static graphs, the k-core problem is principled and very clear: there is one graph, one degree condition, one maximality condition, a nested hierarchy, and a simple linear-time peeling algorithm. This clarity is a major reason for the popularity of k-core decomposition: it is easy to define, fast to compute, and useful as both an analysis tool and a preprocessing primitive.

In temporal graphs, there is usually not one temporal k-core problem. There is a class of related problems with different assumptions and goals. Some papers assume snapshot sequences, some use timestamped multigraphs, some ask for persistent intervals, some emphasize repeated interaction strength, and some look for local bursts around individual events. The right definition depends on the question being asked.

Recap: Static k-Cores

In a static graph G=(V,E), a k-core is a maximal induced subgraph in which every vertex has degree at least k inside that subgraph.

The k-core decomposition assigns every vertex a core number: the largest k for which that vertex belongs to a k-core. Larger core numbers indicate vertices that sit deeper in the graph's nested hierarchy of cohesive regions.

The peeling algorithm

The standard algorithm repeatedly removes a vertex of minimum current degree and updates the degrees of its neighbors. This gives all core numbers in linear time O(n+m) for a graph with n vertices and m edges.

A toy static graph with nested cores. Peripheral vertices peel first and have core number 1; the yellow vertices remain in the 2-core; the teal clique remains in the innermost 3-core.

What Changes in Temporal Graphs?

Once edges have timestamps, there is no single canonical temporal k-core. The right definition depends on what kind of temporal cohesion is meaningful for the application.

Multiplicity Count repeated temporal edges between pairs of vertices. This captures strong repeated ties but may ignore when the repetitions happened.

Intervals Ask that a k-core exists throughout an interval or query range. This captures persistence, but can be restrictive for sparse snapshot sequences.

Temporal locality Judge each interaction by nearby interactions in time. This captures bursts and fine-grained activity without flattening the network.

Comparison of Algorithmic Techniques

Temporal k-core papers differ not only in their definitions, but also in their computational setting. Some compute a full decomposition once, some answer many repeated queries, and some update results as the temporal graph changes.

Peeling and decomposition

Static k-core uses vertex peeling. Temporal variants often adapt this idea to the chosen temporal object: vertices in snapshot projections, vertex-interval pairs in span-cores, or temporal edges in (k, Delta)-cores.

Example: the (k, Delta)-core peels temporal edges by local Delta-degree.

Indexing for repeated queries

Historical, time-range, frequency-aware, and interaction-intensive queries often build indexes so that many future queries can be answered quickly. The tradeoff is preprocessing time and memory.

Examples: PHC-style historical indexes, MCTS core time shells, tree indexes for (k,h)-core queries, and core-frequency indexes.

Online computation

Online algorithms avoid storing a large index and compute answers directly from the graph and query parameters. They are attractive for one-off queries or memory-constrained settings, but can be slower when many queries are issued.

Example: an online (k,h)-core query can avoid index construction but pays more per query.

Incremental maintenance

Maintenance algorithms update core information after insertions or deletions instead of recomputing everything. This is useful when the graph changes continuously and queries must reflect the latest state.

Example: temporal core maintenance for (k,h)-cores under dynamic updates.

Pruning and dominance

Interval-based models can have quadratically many candidate intervals. Algorithms therefore rely on containment, dominance, tightest intervals, maximality tests, and pruning rules to avoid redundant core computations.

Examples: maximal span-cores, time-range k-core queries, and user-defined temporal (k,X)-core queries.

Approximation and optimization

Some tasks are not just decompositions but optimization problems, such as selecting diverse lasting cohesive subgraphs. These can become NP-hard, so greedy or bounded-search approaches with approximation guarantees or practical pruning are used.

Example: diversified top-r lasting cohesive subgraph mining uses approximation-oriented selection.

Applications of Different Approaches

Different temporal core definitions are useful because they answer different application questions. The same dataset can lead to different conclusions depending on whether we care about repeated ties, persistence, bursts, or query-time exploration.

Repeated relationship strength

Multiplicity-based and interaction-intensive cores are appropriate when repeated contact is the signal. In a collaboration graph, this can identify groups with repeated joint work; in a communication graph, it can reveal pairs whose ties are not one-off events.

Persistent communities

Span, lasting, stable, and persistent cores are useful when the goal is to find communities that remain cohesive over time, such as stable teams, recurring social groups, or long-running biological or ecological structures.

Bursts and coordinated activity

Bursting cores and (k, Delta)-cores are useful when timing is the main signal. Examples include detecting coordinated misinformation campaigns, event-driven email bursts, market activity, or emergency-response communication patterns.

Interactive graph analytics

Historical, time-range, user-defined, and frequency-aware query models are designed for analysts who issue many queries with different intervals, thresholds, or constraints. Indexes make exploratory analysis practical.

Monitoring evolving systems

Maintenance algorithms fit streaming or frequently updated graphs, where recomputing all cores after every update is too expensive. Examples include online platforms, transaction networks, and communication services.

Preprocessing and summarization

Temporal core numbers can summarize large temporal graphs before more expensive downstream tasks. They can narrow candidate regions for temporal community search, anomaly detection, visualization, or case-study analysis.

Temporal k-Core and Related Papers

Year	Paper	Category	Model or task	Algorithmic approach	Main idea
2015	Core Decomposition in Large Temporal Graphs Wu et al.	interaction strength	(k,h)-core	Distributed decomposition	Requires at least k neighbors and at least h temporal edges to each neighbor.
2018	Persistent Community Search in Temporal Networks Li, Su, Qin, Yu, Dai	persistence	(theta,tau)-persistent k-core	Reduction, branch-and-bound, pruning	Searches for k-core-like communities that persist under a sliding-window condition.
2020	Efficient Temporal Core Maintenance of Massive Graphs Bai, Chen, Wu	dynamic maintenance	(k,h)-core maintenance	Incremental update algorithms	Maintains temporal cores efficiently under insertions and deletions.
2020	Span-core Decomposition for Temporal Networks: Algorithms and Applications Galimberti et al.	interval persistence	(k,I)-span-core	Interval decomposition with containment pruning	Associates each core with an interval I over which the coreness condition holds.
2020	Mining Stable Communities in Temporal Networks by Density-Based Clustering Qin et al.	stability	(mu,tau,epsilon)-stable core	Density-based clustering with pruning	Looks for vertices with enough similar neighbors across enough snapshots.
2020	Efficient Algorithms to Mine Maximal Span-Trusses from Temporal Graphs Lotito, Montresor	interval truss	span-truss	Maximal interval enumeration and pruning	Temporal analogue of span-cores using k-truss cohesion instead of degree.
2021	Maximum (L,K)-Lasting Cores in Temporal Social Networks Hung, Tseng	lasting community	(L,K)-lasting core	Search over duration-constrained cores	Finds k-cores with k at least K that last for a specified duration L.
2021	Mining Diversified Top-r Lasting Cohesive Subgraphs on Temporal Networks Lin, Yuan, Li, Jin	diverse selection	lasting cohesive subgraphs	Greedy approximation and DFS search	Ranks lasting temporal cohesive subgraphs while encouraging diversity.
2021	On Querying Historical k-Cores Yu, Wen, Qin, Zhang, Zhang, Lin	historical query	historical k-core query	Index-based retrieval and maintenance	Indexes and answers k-core queries over fixed historical intervals.
2022	Mining Bursting Core in Large Temporal Graphs Qin et al.	burst detection	(l,delta)-bursting core	Dynamic programming and dominance pruning	Finds communities whose average degree is high during a sufficiently long burst.
2023	KWIQ: Answering k-Core Window Queries in Temporal Networks Momin, Kamal, Dixit, Ranu, Bagchi	window query	core-invariant nodes	Orientation graph and pruning	Finds nodes whose core number stays above a threshold throughout a window.
2023	Scalable Time-Range k-Core Query on Temporal Graphs Yang, Zhong, Zhu, Qian, Liu, Yu	time-range query	time-range k-core query	Temporal decomposition, TTI pruning, online query	Returns distinct k-cores induced by subintervals of a query interval.
2023	A Higher-Order Temporal H-Index for Evolving Networks Oettershagen, Kriege, Mutzel	temporal ranking	(eta,k)-pseudocore	Recursive temporal H-index computation	Uses a higher-order temporal H-index to identify components with strong communication capability.
2024	A Unified and Scalable Algorithm Framework of User-Defined Temporal (k,X)-Core Query Zhong et al.	unified query	user-defined temporal core query	Two-phase framework with metric-aware pruning	Generalizes temporal k-core queries with additional user-defined constraints or objectives.
2025	Querying Historical K-Cores in Large Temporal Graphs Yu, Wen, Yu, Qin, Zhang, Zhang, Lin	historical query	historical k-core query	Index-based retrieval, pruning, index maintenance	Journal version of the historical k-core query work with index-based retrieval, pruning, and index maintenance.
2025	On More Efficiently and Versatilely Querying Historical k-Cores Wang, Zhong, Zhu, Qian, Liu, Yu	historical query	core time shell	MCTS index and core time shell hierarchy	Introduces core time shells and an MCTS index for faster historical k-core queries and new "when" query variants.
2025	Efficient Frequency-Aware k-Core Query on Temporal Graphs Du, Zhong, Zhu, Qian, Liu, Yu	frequency query	frequency-aware k-core	Core-frequency index and skyline retrieval	Requires k-core neighbors to have enough high-frequency interactions and indexes core frequencies for efficient queries.
2025	An Edge-Based Decomposition Framework for Temporal Networks Oettershagen, Konstantinidis, Italiano	edge-local decomposition	(k,Delta)-core and truss	Temporal edge peeling and Delta-components	Peels temporal edges by local temporal edge degree or temporal triangle support.
2025	Mining Interaction-Intensive Cores in Temporal Graphs Zhou, Gong, Lu, Liang, Wen	interaction query	(k,h)-core query	Online baseline, full index, tree indexes	Builds compact tree-style indexes for querying interaction-intensive (k,h)-cores.

Choosing a Definition

Use a multiplicity-based core such as (k,h)-core when repeated interaction strength matters more than the precise placement of timestamps. Use span, lasting, persistent, or query-based cores when the target is an interval-level question. Use edge-local definitions such as (k,Delta)-cores when the goal is to capture fine-grained temporal neighborhoods, bursts, or temporally coordinated activity.