UCR: Upper-bound Core Ranking for Sliding-Window $k$-Core Maintenance

UCR is an exact, output-sensitive algorithm for maintaining the $k$-core decomposition of a temporal graph under a sliding window, where each update simultaneously deletes expired edges and inserts newly arrived ones.

Each vertex keeps two $O(1)$-maintained counters — the $r$-value (neighbors with a strictly higher core number) and the $s$-value (neighbors with the same core number). Their sum is a sound upper bound that prunes the candidate set; a localized peeling then resolves the exact core-number changes. Updates are processed per batch (a whole window slide at once) and, for initialization, with a parallel cold start.

Every result produced by the experiments is verified to be identical to a from-scratch Batagelj–Zaveršnik (BZ) recomputation (0 mismatches).

Requirements

• A C++17 compiler with OpenMP (e.g. g++ 9 or newer)
• Python 3 with matplotlib and numpy (only needed to regenerate the figures)

Repository layout

UCR/
├── src/                     # header-only implementation
│   ├── graph.hpp            # static graph (sorted-vector adjacency)
│   ├── graph_fast.hpp       # cache-friendly adjacency variant
│   ├── partial_loader.hpp   # streaming edge-list loader
│   ├── config.hpp           # dataset registry + output directory
│   ├── bz.hpp               # Batagelj–Zaveršnik static decomposition (ground truth)
│   ├── ucr_rs.hpp           # UCR: r/s counters + localized peeling (main algorithm)
│   ├── ucr_rs_g.hpp         # UCR templated over the graph type
│   ├── ucr_par.hpp          # UCR with parallel cold-start + component-parallel insert
│   ├── par_core.hpp         # parallel peeling (exact, used by the cold start)
│   ├── mcd.hpp, mcd_g.hpp   # MCD/PCD traversal baseline
│   └── order_based_real.hpp # order-based baseline (Zhang et al., ICDE 2017)
├── exp/                     # experiment drivers and correctness tests
├── plot/                    # figure generation (Matplotlib)
├── results/                 # experiment output (.txt) consumed by the plots
├── datasets/                # input graphs (you provide; see below)
├── build.sh                 # compile experiments and tests
└── README.md

Datasets

Each input is a plain-text temporal edge list, one edge per line:

u v t      # source  destination  integer-timestamp  (whitespace-separated)

Lines beginning with # or % are ignored; self-loops are skipped. Put each file under datasets/ with the names referenced in src/config.hpp:

Name in config.hpp	Source
sx-superuser	SNAP (snap.stanford.edu/data)
sx-stackoverflow	SNAP
wiki-talk-temporal	SNAP
cit-Patents	SNAP
soc-LiveJournal1	SNAP
bitcoin-temporal	public temporal-graph repositories
temporal-reddit-reply	public temporal-graph repositories
social_media_100M	synthetic (TGX temporal-graph toolkit)

Any temporal edge list in the u v t format will work — edit config.hpp to add your own.

Build

./build.sh          # compile all experiments + correctness tests into ./bin/
./build.sh tests    # only the correctness tests

Or compile a single driver manually:

g++ -O2 -std=c++17 -fopenmp exp/exp_sliding_fast.cpp -o bin/exp_sliding_fast

Reproducing the paper results

Run from the repository root; each driver writes a .txt into results/ and validates its output against BZ at every step.

Experiment (./bin/…)	Output file	Paper result
exp_batch_fast	results/exp_batch_fast.txt	batch-update time (UCR vs MCD/PCD)
exp_orderbased	results/exp_orderbased.txt	search region: UCR vs order-based/MCD
exp_sliding_fast	results/exp_sliding_fast.txt	sliding-window speedup over BZ
exp_parallel_cold	results/exp_parallel.txt	parallel cold-start speedup
exp_boundary	results/exp_boundary.txt	crossover $\beta^\star$
exp_case_study	results/exp_case_study.txt	interactive analyst workflow
exp_vertexaccess	results/exp_vertexaccess.txt	vertices visited per batch

Then regenerate the figures:

python3 plot/plot_results.py          # main result figures
python3 plot/plot_running_example.py  # the worked r/s example

API sketch

#include "src/graph.hpp"
#include "src/ucr_rs.hpp"

StaticGraph g;
g.init(num_vertices);
for (auto [u, v] : initial_edges) g.addEdge(u, v);

UCRrs ucr;
ucr.init(&g);                 // cold-start decomposition + r/s

ucr.removeEdges(expired);     // a sliding-window step:
ucr.insertEdges(arrived);     //   delete then insert (as a batch)

const std::vector<int>& core = ucr.getCoreNumbers();

For the parallel cold start and component-parallel insertion, use UCRPar from src/ucr_par.hpp.

Correctness

Correctness is verified two ways: (1) every experiment compares UCR's full core-number vector to a BZ recomputation at each batch/slide and reports any mismatch; (2) dedicated tests exhaustively check small graphs, long random insert/delete sequences, batch paths, and adversarial clique/bowtie cases:

./bin/test_ucr_rs          # UCR vs BZ + r/s invariants (0 mismatches expected)
./bin/test_r1_adversarial  # clique / Lemma-1 adversarial cases
./bin/test_order_based     # order-based baseline vs BZ

License

MIT License.