API reference

TemporalGraphs

A Julia library for temporal graph analysis: temporal distances and paths, temporal centralities (closeness, betweenness, Katz, PageRank, walk centrality), connectivity, flows, spanners, motifs, isomorphisms, randomized reference models, generators of temporal graph classes and other local and global temporal graph statistics and parameters.

The package was inspired by TGLib (https://gitlab.com/tgpublic/tglib, Lutz Oettershagen and Petra Mutzel), whose functionality it covers with its own Julia design and algorithms.

The graph types are parametric in the node id type V and the time type T (integers or floating point numbers). Node ids are 1-based. Every temporal edge (u, v, t, tt) goes from u to v, departs at time t and arrives at time t + tt. Algorithms can be restricted to a time interval (a, b): an edge is usable iff a ≤ t and t + tt ≤ b.

References

• L. Oettershagen and P. Mutzel. TGLib: an open-source library for temporal graph analysis. IEEE International Conference on Data Mining Workshops (ICDMW), 2022. DOI, arXiv

TemporalEdge{V<:Integer,T<:Real}(u, v, t, tt = 1)
TemporalEdge(u, v, t, tt = 1)

A directed temporal edge from u to v that departs at time t and needs the transition time tt, i.e., it arrives at v at time t + tt.

V is the node id type and T the time type (integer or floating point times). Without explicit parameters node ids are stored as Int32 (an edge with Int64 times takes 24 bytes) and T is the promoted type of t and tt. Edges are ordered lexicographically by (t, tt, u, v).

TimeInterval{T}

A closed time interval (a, b). Algorithms restricted to (a, b) only use edges e with a ≤ e.t and e.t + e.tt ≤ b.

INF

typemax(Int64), the distance of unreachable nodes in graphs with Int64 times. In general unreachable nodes get typemax(T) (Inf for floating point times).

TemporalDistances(A::AbstractArray)

The vector or matrix A of distances or times, wrapped without copying, that prints the entries of unreachable nodes (typemax, i.e. INF for Int64 times, and typemin for latest departure times) as ∞ and -∞. Otherwise it behaves as A: the entries keep their values, so d[v] == INF tests if v is unreachable, and parent(d) returns A. Returned by temporal_distances and the functions based on it, earliest_arrival_matrix and temporal_flooding_times.

StaticWeightedEdge(u, v, weight)

A static (non-temporal) edge with an integer weight, e.g., the number of temporal contacts between u and v.

DistanceType

Abstract supertype of the notions of optimal temporal paths: EarliestArrival, Fastest, LatestDeparture, MinimumTransitionTimes and MinimumHops, and the criteria ShortestForemost, ShortestFastest, ShortestLatest and PrefixForemost, which only select optimal walks for the betweenness. They are singleton types, so the algorithms are specialized at compile time for each of them.

Earliest arrival paths: the distance is the arrival time.

Fastest paths: the distance is the duration (arrival time minus departure time).

Latest departure paths: the latest time one can leave the source.

Shortest paths: the distance is the sum of the transition times.

Minimum hop paths: the distance is the number of edges.

Shortest foremost walks: earliest arrival, ties broken by the number of edges. Only used by the betweenness functions, see temporal_betweenness.

Shortest fastest walks: minimum duration, ties broken by the number of edges. Only used by the betweenness functions, see temporal_betweenness.

Shortest latest walks: latest departure, ties broken by the number of edges. Only used by the betweenness functions, see temporal_betweenness.

Prefix foremost paths (Buß et al., 2020): foremost paths whose every prefix is also foremost, i.e., every node is reached at its earliest arrival time. Only used by the betweenness functions, see temporal_betweenness.

OrderedEdgeList(n, edges, ti = span(edges); original_ids = 1:n)

Temporal graph with nodes 1:n stored as a chronologically ordered list of temporal edges (the "edge stream" representation). This is the main representation: most algorithms run a single scan over the contiguous edge vector.

edges is a vector of TemporalEdges or of tuples (u, v, t, tt). It is copied, and sorted by (t, tt, u, v) if it is not sorted by time; otherwise its order is kept, except that the edges with transition time 0 come first among those with the same time stamp. ti is the time interval spanned by the graph and defaults to (minimum t, maximum t + tt). original_ids[i] is the id that node i had in the input file (see load_ordered_edge_list).

IncidentLists(n, edges, ti = span(edges))

Temporal graph in incident lists representation: for every node the outgoing temporal edges in chronological order. The lists are stored contiguously in one vector (compressed sparse row layout); out_edges(g, u) returns a view.

TRSGraph

Time-respecting static graph: a static DAG equivalent to a temporal graph with respect to reachability, used for temporal distance computations.

Every TRS node is a time-node (v, τ), i.e., a node v of the temporal graph at a time τ at which v has an outgoing edge (plus the latest arrival time at v). Time-nodes of the same node are consecutive and sorted by time, and they are chained by waiting edges with transition time 0. A temporal edge (u, v, t, tt) becomes an edge from (u, t) to the earliest time-node (v, τ) with τ ≥ t + tt. Construct it with to_trs_graph.

DirectedLineGraph

Directed line graph of a temporal graph. Node i represents the temporal edge edges(dlg)[i], and there is an edge from e = (u, v, t, tt) to f iff f leaves v and f.t ≥ t + tt, i.e., (e, f) is a temporal path of length two. Construct it with to_directed_line_graph.

num_nodes(g)

Number of nodes of the temporal graph g.

num_edges(g)

Number of (temporal) edges of g.

edges(g)

The temporal edges of g (this extends Graphs.edges).

time_interval(g)

The time interval (a, b) spanned by g.

time_type(g)

The type of the time stamps of g.

node_type(g)

The type of the node ids stored in the edges of g.

out_edges(g::IncidentLists, u)

The outgoing temporal edges of u in chronological order (a view).

out_edges(dlg::DirectedLineGraph, i)

The out-neighbors of node i of the directed line graph.

out_degree(g::IncidentLists, u)

Number of outgoing temporal edges of u.

original_id(g, u)

The id node u had in the input file.

original_ids(g)

Vector mapping each node to the id it had in the input file.

node_map(g)

Dictionary mapping the ids of the input file to the node ids of g.

num_trs_nodes(g::TRSGraph)

Number of time-nodes of the TRS graph.

trs_node(g::TRSGraph, i)

The temporal graph node of time-node i.

trs_time(g::TRSGraph, i)

The time of time-node i.

trs_neighbors(g::TRSGraph, i)

The out-neighbors of time-node i and the corresponding transition times, as a tuple of two vectors. The waiting edge, if any, comes first.

load_ordered_edge_list(filename; directed = true, default_tt = 1,
                       time_type = Int64, node_type = Int32)

Load a temporal graph from a text file in which each line u v t [tt] is a temporal edge (separated by spaces, tabs or commas; lines starting with # or % and lines with fewer than three values are skipped; missing transition times are default_tt; further columns are ignored). Use time_type = Float64 for real-valued times.

Node ids are mapped to 1:n in order of first appearance, the ids of the file are available via original_id. If directed is false, every edge is inserted in both directions.

load_incident_lists(filename; kwargs...)

Load a temporal graph in IncidentLists representation, see load_ordered_edge_list.

load_trs_graph(filename; kwargs...)

Load a temporal graph in TRSGraph representation, see load_ordered_edge_list.

save_ordered_edge_list(filename, g::OrderedEdgeList; original_ids = true)

Write g in the format read by load_ordered_edge_list, one line u v t tt per edge. With original_ids = true the node ids of the input file are used.

OrderedEdgeList(table; u = 1, v = 2, t = 3, tt = nothing, directed = true,
                default_tt = 1, node_type = Int32)

Build a temporal graph from any table supported by Tables.jl (e.g., a DataFrame or a CSV.File). u, v, t and tt are the column names or indices of the tails, heads, time stamps and transition times; without a tt column all transition times are default_tt. Node ids (integers) are mapped to 1:n in order of first appearance, as in load_ordered_edge_list.

to_ordered_edge_list(g::IncidentLists)

Transform g into its OrderedEdgeList representation.

to_incident_lists(g::OrderedEdgeList)

Transform g into its IncidentLists representation.

to_trs_graph(g::OrderedEdgeList)

Transform g into its time-respecting static graph representation TRSGraph.

to_directed_line_graph(g)

Directed line graph of g. For an OrderedEdgeList, node i of the result is the i-th edge of edges(g); for IncidentLists it is the i-th edge of edges(g) in incident lists order.

to_aggregated_edge_list(g::OrderedEdgeList)

The static graph underlying g in which every edge (u, v) is weighted with the number of temporal edges from u to v. The result is sorted by (u, v).

static_graph(g::OrderedEdgeList, ti = nothing; directed = true)

The static graph underlying g as a Graphs.SimpleDiGraph (or SimpleGraph if directed = false), with an edge (u, v) iff there is a temporal edge from u to v. With a time window ti = (a, b), only the edges with time stamps in [a, b] are used (the window graph; see also window_components and snapshots). Use to_aggregated_edge_list for the contact counts.

snapshots(g::OrderedEdgeList, ti = nothing; resolution = nothing, directed = true)

The snapshot graphs of g: the time interval ti = (a, b) (by default from the start of the time interval of g to its last time stamp) is cut into steps [a, a + Δ), [a + Δ, a + 2Δ), … of length Δ = resolution, and the snapshot of a step is the static graph (a Graphs.SimpleDiGraph, or SimpleGraph if directed = false) of the edges whose time stamp falls in it. By default Δ is the resolution of the time stamps (the gcd of the times minus a), so that every time stamp has its own snapshot and empty steps give empty snapshots; a larger Δ aggregates the edges of every step (see also aggregate_time). For floating point times without resolution there is one snapshot per distinct time stamp.

Returns (times, graphs), where times[k] is the start of step k. Multiple edges of a step become one edge of the snapshot. OrderedEdgeList(graphs, times) converts a sequence of snapshots back into a temporal graph.

OrderedEdgeList(graphs::AbstractVector{<:Graphs.AbstractGraph}, times = 1:length(graphs);
                transition_time = 1, node_type = Int32)

The temporal graph of a sequence of snapshot graphs: every edge (u, v) of graphs[k] becomes the temporal edge (u, v, times[k], transition_time), in both directions for undirected graphs. The default transition time 1 with consecutive integer times gives strict paths, which use at most one edge per snapshot; use transition_time = 0 for non-strict paths through several edges of a snapshot. All graphs must have the same number of nodes. The time interval is (times[1], times[end] + transition_time).

aggregate_time(g::OrderedEdgeList, Δ, ti = time_interval(g); transition_time = nothing,
               multiedges = false)

Reduce the time resolution of g to Δ: every edge inside ti = (a, b) (by its time stamp) is moved to the start a + kΔ of its step [a + kΔ, a + (k+1)Δ), for example from seconds to hours. Edges that become identical are merged unless multiedges. The transition times are kept, or all set to transition_time (Δ makes the paths strict at the new resolution, 0 non-strict). The result has the same nodes; its time interval covers the steps.

normalize_graph(g::OrderedEdgeList, remove_loops::Bool = true)

Remove multiple (identical) edges and, if remove_loops, self-loops. The resulting edges are sorted by (t, tt, u, v) and the time interval is recomputed.

scale_timestamps(g::OrderedEdgeList, factor)

Multiply all time stamps by factor (for integer times rounding half away from zero) and remove the resulting multiple edges.

unit_transition_times(g::OrderedEdgeList, val = 1)

Replace all transition times by val.

make_undirected(g::OrderedEdgeList)

Insert for each edge (u, v, t, tt) the reverse edge (v, u, t, tt) and remove multiple edges.

reverse(g, ti = time_interval(g))

Temporal transpose (reverse temporal graph) of g restricted to ti = (a, b), see Oettershagen and Mutzel, "Efficient top-k temporal closeness calculation in temporal networks", ICDM 2020. Each edge (u, v, t, tt) inside ti becomes (v, u, a + b - t - tt, tt), so that a path from u to w with duration d becomes a path from w to u with duration d and the interval is preserved.

References

• L. Oettershagen and P. Mutzel. Efficient top-k temporal closeness calculation in temporal networks. ICDM, 2020. DOI

draw_graph(g; positions = nothing, node_labels = 1:n, node_colors = Julia colors,
           edge_labels = true, width = 420, node_radius = 20)

Draws the temporal graph g as its static graph: one arrow from u to v for every temporal edge (u, v, t, tt), labelled with (t, tt) if edge_labels. The edges between the same two nodes are drawn as separate arcs and self-loops as loops. Returns a TemporalGraphDrawing; see draw_timelines for a drawing that shows the times.

The nodes are placed on a circle, unless positions[i] = (x, y) gives the position of node i (with y pointing up, in any unit: the drawing is scaled to width pixels). node_colors is cycled over the nodes. Meant for small graphs: every edge is drawn.

draw_timelines(g, ti = time_interval(g); order = 1:n, node_labels = 1:n,
               node_colors = Julia colors, width = 600, row_height = 70)

Draws the temporal graph g with one horizontal timeline per node and time on the horizontal axis: every temporal edge (u, v, t, tt) is an arrow from the timeline of u at time t to the timeline of v at time t + tt, and the dots mark the departures and arrivals. Returns a TemporalGraphDrawing; see draw_graph for the static graph.

ti = (a, b) is the time range of the axis; only the edges inside it are drawn. order lists the nodes from top to bottom (a subset of the nodes draws only the edges between them); changing it can avoid arrows that cross the dots of other nodes. node_colors is cycled over the nodes. Meant for small graphs: every edge is drawn.

TemporalGraphDrawing

An SVG drawing of a temporal graph, returned by draw_graph and draw_timelines. Notebooks, the VS Code plot pane and Documenter display it as an image (MIME"image/svg+xml"); write("file.svg", d) saves it and String(d) returns its SVG source.

temporal_distances(g, s, dt::DistanceType, ti = time_interval(g); β = Inf)

Temporal distances of type dt from s to all nodes of g inside the time interval ti, for an OrderedEdgeList, IncidentLists or TRSGraph, as a TemporalDistances vector. Unreachable nodes get typemax of the element type (for LatestDeparture typemin), printed as ∞ (-∞).

With a finite β (only for an OrderedEdgeList) the distances are those of β-restless walks (Casteigts, Himmel, Molter and Zschoche, 2021), which wait at most β at every intermediate node: every edge departs in [a, a + β], where a is the arrival time of the previous edge, and the departure from s is free. Such walks can visit a node several times (finding restless paths is NP-hard, see restless_path). They are computed in O(m log m) time with one scan of the edges and a sliding window of the arrivals at every node.

For repeated computations use the in-place temporal_distances! with a distance_workspace, which avoids all allocations.

References

• H. Wu, J. Cheng, Y. Ke, S. Huang, Y. Huang, and H. Wu. Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering 28(11), 2016. DOI
• A. Casteigts, A.-S. Himmel, H. Molter, and P. Zschoche. Finding temporal paths under waiting time constraints. Algorithmica 83(9), 2021. DOI, arXiv

temporal_distances!(dist, ws, g, s, dt::DistanceType, ti = time_interval(g))

In-place version of temporal_distances: writes the distances from s into dist (a vector of length num_nodes(g) and element type distance_eltype(g, dt)), using the buffers ws = distance_workspace(g, dt). Returns dist.

distance_workspace(g, dt::DistanceType)

Buffers for temporal_distances!. Repeated single-source computations with the same workspace do not allocate once the buffers have grown to their final size. A workspace must not be shared between tasks running in parallel.

distance_eltype(g, dt::DistanceType)

Element type of the distance vectors computed for g and dt: Int for MinimumHops, the time type of g otherwise.

earliest_arrival_times(g, s, ti = time_interval(g))

Earliest arrival times at all nodes for paths starting at s inside ti. Unreachable nodes get typemax, the source gets 0.

latest_departure_times(g, s, ti = time_interval(g))

For every node v, the latest time at which one can leave s and still reach v inside ti. Unreachable nodes get typemin, the source gets ti[2]. Implemented for OrderedEdgeList and IncidentLists.

minimum_durations(g, s, ti = time_interval(g))

Durations of fastest paths from s to all nodes inside ti (arrival time minus departure time). Unreachable nodes get typemax, the source gets 0.

minimum_transition_times(g, s, ti = time_interval(g))

Minimum sum of transition times of temporal paths (shortest paths) from s to all nodes inside ti. Unreachable nodes get typemax, the source gets 0.

minimum_hops(g, s, ti = time_interval(g))

Minimum number of edges of temporal paths from s to all nodes inside ti (typemax(Int) for unreachable nodes).

number_of_reachable_nodes(g::OrderedEdgeList, s, ti = time_interval(g))

Number of nodes reachable from s inside ti, including s itself.

StreamWorkspace

Reusable buffers for temporal distance computations on an OrderedEdgeList, created by distance_workspace.

IncidentListsWorkspace

Reusable buffers for temporal distance computations on IncidentLists, created by distance_workspace.

TRSWorkspace

Reusable buffers for temporal distance computations on a TRSGraph, created by distance_workspace.

earliest_arrival_path(g, s, target, ti = time_interval(g))

An earliest arrival path from s to target inside ti as a vector of temporal edges; empty if target is not reachable or equal to s.

minimum_duration_path(g, s, target, ti = time_interval(g))

A fastest path from s to target inside ti; empty if there is none.

minimum_transition_time_path(g, s, target, ti = time_interval(g))

A path with minimum sum of transition times from s to target inside ti; empty if there is none.

minimum_hops_path(g, s, target, ti = time_interval(g))

A path with the minimum number of edges from s to target inside ti; empty if there is none.

temporal_closeness(g, s, dt::DistanceType, ti = time_interval(g))

Temporal closeness of node s: the sum of 1/d(s, v) over all nodes v with 0 < d(s, v) < ∞, where d is the temporal distance of type dt (for EarliestArrival the arrival time, for LatestDeparture ti[2] minus the latest departure time).

temporal_closeness(g, dt::DistanceType, ti = time_interval(g))

Temporal closeness of all nodes. Runs in parallel when Julia is started with several threads.

compute_topk_closeness(g, k, dt::DistanceType, ti = time_interval(g))

The k nodes with the highest temporal closeness as a vector of (node, closeness) pairs by decreasing closeness; nodes with equal closeness are all returned.

For Fastest and MinimumTransitionTimes the pruning algorithm of Oettershagen and Mutzel (ICDM 2020) is used, for other distance types the closeness of all nodes is computed.

References

• L. Oettershagen and P. Mutzel. Efficient top-k temporal closeness calculation in temporal networks. ICDM, 2020. DOI

temporal_closeness_approximation(g, h, ti = time_interval(g); rng = Random.default_rng())

Estimate the fastest path temporal closeness of all nodes from h samples: for uniformly random nodes w, the durations towards w are computed on the reversed temporal graph, and the sums are scaled by n / h, which gives an unbiased estimate.

temporal_harmonic_closeness(g::OrderedEdgeList, ti = time_interval(g))

Temporal closeness of all nodes averaged over the departure time (Crescenzi, Magnien and Marino, 2020):

C(s) = 1 / ((n - 1)(b - a)) Σ_{v ≠ s} ∫_a^b dτ / ℓ_τ(s, v),

where (a, b) = ti and the latency ℓ_τ(s, v) is the earliest arrival time at v when leaving s at time τ or later, minus τ. Unreachable nodes contribute 0. Only edges inside ti are used and transition times must be positive. The integral is computed exactly from the Pareto fronts of (arrival, departure) pairs in one scan of the edges per node; nodes are processed in parallel.

References

• P. Crescenzi, C. Magnien, and A. Marino. Finding top-k nodes for temporal closeness in large temporal graphs. Algorithms 13(9), 2020. DOI

temporal_harmonic_closeness(g::OrderedEdgeList, s, ti = time_interval(g))

Temporal closeness of node s averaged over the departure time, see above.

temporal_harmonic_closeness_approximation(g::OrderedEdgeList, samples, ti = time_interval(g);
                                          rng = Random.default_rng())

Unbiased estimate of temporal_harmonic_closeness of all nodes (Crescenzi, Magnien and Marino, 2020): for samples uniformly random target nodes d, the contributions of d to the closeness of all nodes are computed with one backward scan (a forward scan of the reversed temporal graph), and the sums are scaled by n / samples. The estimates are most accurate for the nodes with the highest closeness, which makes them suited to find the top-k nodes.

References

• P. Crescenzi, C. Magnien, and A. Marino. Finding top-k nodes for temporal closeness in large temporal graphs. Algorithms 13(9), 2020. DOI

temporal_eccentricity(g, s, dt::DistanceType, ti = time_interval(g))

The largest finite temporal distance of type dt from s (0 if no other node is reachable), with distances as in temporal_closeness.

temporal_diameter(g, dt::DistanceType, ti = time_interval(g))

The largest temporal eccentricity over all nodes. Runs in parallel when Julia is started with several threads.

temporal_efficiency(g, dt::DistanceType, ti = time_interval(g))

Global temporal efficiency: the sum of the temporal closeness of all nodes divided by n(n - 1).

temporal_distance_statistics(g::OrderedEdgeList, criterion = MinimumHops();
                             samples = nothing, τ = 0.9, rng = Random.default_rng())

Statistics of the lengths (numbers of edges) of the optimal temporal paths of type criterion (MinimumHops(), ShortestForemost() or PrefixForemost(), for which the fewest edges among the prefix foremost paths is used): a named tuple with

• diameter: the largest length,
• effective_diameter: the smallest h such that a fraction τ of the connected pairs are at distance at most h,
• connectivity_rate: the fraction of ordered pairs of distinct nodes that are temporally connected,
• average_distance: the average length over the connected pairs.

By default all nodes are used as sources (exact values, in parallel). With samples = r the statistics are estimated from r random sources as in Algorithm 2 of Cruciani (2024); r = Θ(log(n) / ε²) sources give the connectivity rate within ε with high probability (the diameter estimate is a lower bound).

References

• A. Cruciani. MANTRA: temporal betweenness centrality approximation through sampling. ECML PKDD, 2024. DOI, arXiv

temporal_betweenness(g::OrderedEdgeList, criterion = MinimumHops(), ti = time_interval(g);
                     β = Inf, count_type = nothing)

Temporal betweenness of all nodes: for every node u, the sum over all pairs of nodes s ≠ t different from u, with t reachable from s, of the fraction of the optimal temporal walks from s to t that pass through u (walks passing several times through u are counted with multiplicity).

The optimality criterion is one of

β is the maximum waiting time at a node (restless walks); β = Inf means no constraint. Only edges inside the time window ti are used.

Positive transition times give strict walks. Edges with transition time 0 give non-strict walks (Zhang et al., WWW 2024): such an edge can be followed at once by another edge with the same time stamp. If the edges with transition time 0 and the same time stamp form a cycle that a walk can reach, there are infinitely many optimal walks for every criterion except the shortest ones (MinimumHops, ShortestForemost, ShortestLatest, ShortestFastest), and an ArgumentError is thrown. Prefix foremost betweenness requires positive transition times.

By default (count_type = nothing) the numbers of optimal walks are counted in Float64; if they overflow (typical for foremost and fastest walks on large graphs, whose optimal walks are very numerous) the computation is repeated with BigFloat. Pass count_type = BigFloat to use it directly, or count_type = Rational{BigInt} to count the walks and compute the contribution of every source exactly. The result is a Vector{Float64} in every case: the contributions are rounded to Float64 and summed.

With MinimumHops() and no waiting constraint this is the shortest temporal betweenness of Buß et al. (KDD 2020), since shortest strict walks are paths. The algorithm follows the approach of Brunelli, Crescenzi and Viennot (KDD 2024) and runs in O(n M) time without waiting constraint and O(n M log M) with it (M edges); sources are processed in parallel.

References

• F. Brunelli, P. Crescenzi, and L. Viennot. Making temporal betweenness computation faster and restless. KDD, 2024. DOI, arXiv
• S. Buß, H. Molter, R. Niedermeier, and M. Rymar. Algorithmic aspects of temporal betweenness. KDD, 2020. DOI, arXiv
• T. Zhang, Y. Gao, J. Zhao, L. Chen, L. Jin, Z. Yang, B. Cao, and J. Fan. Efficient exact and approximate betweenness centrality computation for temporal graphs. The Web Conference (WWW), 2024. DOI

temporal_ego_betweenness(g::OrderedEdgeList, criterion = MinimumHops(), ti = time_interval(g);
                         β = Inf, count_type = nothing)

Temporal ego-betweenness (Becker et al., 2023): for every node v, the temporal betweenness of v (see temporal_betweenness, same criteria) in its ego network, the temporal subgraph induced by v and its in- and out-neighbors. A local proxy of the temporal betweenness. Nodes are processed in parallel.

References

• R. Becker, P. Crescenzi, A. Cruciani, and B. Kodric. Proxying betweenness centrality rankings in temporal networks. SEA, 2023. DOI

temporal_pass_through_degree(g::OrderedEdgeList, ti = time_interval(g))

Temporal pass-through degree (Becker et al., 2023): for every node u, the square root of the number of ordered pairs (v, w) of nodes different from u (possibly v = w) such that some edge from v to u is followed in time by some edge from u to w, i.e., the earliest arrival of an edge v → u is not later than the latest departure of an edge u → w. A local proxy of the temporal betweenness computable in O(M log M) time.

References

• R. Becker, P. Crescenzi, A. Cruciani, and B. Kodric. Proxying betweenness centrality rankings in temporal networks. SEA, 2023. DOI

temporal_betweenness_approximation(g::OrderedEdgeList, samples, criterion = MinimumHops(),
                                   ti = time_interval(g); β = Inf, η = 0.1,
                                   rng = Random.default_rng(), count_type = Float64)

Estimate the normalized temporal betweenness b(v) / (n (n - 1)) of all nodes with the ONBRA sampling scheme (Santoro and Sarpe, 2022): samples ordered pairs (s, z) of distinct nodes are drawn uniformly at random and, for each of them, every node other than s and z receives the fraction of optimal s-z walks through it. Returns (estimates, ε) where, with probability at least 1 - η, every estimate is within ε of the exact value (empirical Bernstein bound). The criteria and β are those of temporal_betweenness; multiplicities are counted as there.

References

• D. Santoro and I. Sarpe. ONBRA: rigorous estimation of the temporal betweenness centrality in temporal networks. The Web Conference (WWW), 2022. DOI, arXiv

temporal_betweenness_mantra(g::OrderedEdgeList, criterion = MinimumHops();
                            ε = 0.01, δ = 0.1, estimator = :pairs, mc_trials = 25,
                            max_samples = typemax(Int), rng = Random.default_rng())

Estimate the normalized temporal betweenness b(v) = B(v) / (n (n - 1)) of all nodes up to an absolute error ε with probability at least 1 - δ, with the MANTRA progressive sampling algorithm (Cruciani, 2024). criterion is MinimumHops() (shortest paths), ShortestForemost() or PrefixForemost(); for these criteria the optimal walks are paths and the estimates of each sample lie in [0, 1].

estimator = :pairs samples pairs of nodes (the estimator of ONBRA), :sources samples nodes and uses all their optimal paths. After a bootstrap phase that bounds the variance of the estimators and the average number of internal nodes of the optimal paths, the sample grows by a factor 1.2 until the bound on the maximum error obtained from mc_trials Monte Carlo empirical Rademacher averages is at most ε, or a sufficient sample size is reached. Samples are evaluated in parallel.

The exact temporal_betweenness costs about as much as n samples, so sampling pays off when the required number of samples (which grows as 1/ε²) is much smaller than the number of nodes.

Returns a named tuple (estimates, error_bound, samples).

References

• A. Cruciani. MANTRA: temporal betweenness centrality approximation through sampling. ECML PKDD, 2024. DOI, arXiv

temporal_betweenness_atbc(g::OrderedEdgeList, criterion = MinimumHops();
                          ε = 0.01, δ = 0.1, max_samples = typemax(Int),
                          rng = Random.default_rng())

Estimate the normalized temporal betweenness B(v) / (n (n - 1)) of all nodes up to an absolute error ε with probability at least 1 - δ, with the ATBC progressive sampling algorithm of Zhang et al. (WWW 2024): pairs of nodes are sampled until the bound of Riondato and Upfal (ABRA) on the maximum deviation, computed from the empirical Rademacher average of the sample, is at most ε. The paper considers shortest (MinimumHops()), earliest (EarliestArrival()), fastest (Fastest()) and shortest earliest (ShortestForemost()) paths; strict and non-strict paths correspond to positive and zero transition times. The sample grows by a factor 1.2 between iterations (the paper uses the sample size schedule of ABRA). Samples are evaluated in parallel.

The guarantee assumes that every sample value σ_sz(v) / σ_sz is at most 1, which holds for shortest walks; for earliest and fastest walks that visit a node several times (counted with multiplicity) it can be slightly larger, in which case a warning is issued.

Returns a named tuple (estimates, error_bound, samples).

References

• T. Zhang, Y. Gao, J. Zhao, L. Chen, L. Jin, Z. Yang, B. Cao, and J. Fan. Efficient exact and approximate betweenness centrality computation for temporal graphs. The Web Conference (WWW), 2024. DOI
• M. Riondato and E. Upfal. ABRA: approximating betweenness centrality in static and dynamic graphs with Rademacher averages. ACM Transactions on Knowledge Discovery from Data 12(5), 2018. DOI

temporal_edge_betweenness(dlg::DirectedLineGraph)
temporal_edge_betweenness(g::OrderedEdgeList)

Temporal edge betweenness: Brandes' betweenness of the nodes of the directed line graph, i.e., for every temporal edge the sum over all pairs of edges (e, f) of the fraction of shortest (minimum hop) temporal paths from e to f that use it. Entry i belongs to edges(dlg)[i], respectively edges(g)[i]. The sources are processed in parallel chunks with one accumulator per chunk.

temporal_katz_centrality(g::OrderedEdgeList, beta)

Temporal Katz centrality (Béres et al., 2018): for every node the sum of beta^k over all temporal walks of length k ending at the node. Consecutive edges of a walk have strictly increasing time stamps; transition times are ignored.

References

• F. Béres, R. Pálovics, A. Oláh, and A. A. Benczúr. Temporal walk based centrality metric for graph streams. Applied Network Science 3, 2018. DOI

temporal_pagerank(g::OrderedEdgeList, alpha, beta, gamma)

Temporal PageRank (Rozenshtein and Gionis, 2016) as implemented in TGLib, with restart probability 1 - alpha, transition probability beta and decay gamma.

References

• P. Rozenshtein and A. Gionis. Temporal PageRank. ECML PKDD, 2016. DOI

temporal_walk_centrality(g::OrderedEdgeList, alpha, beta)

Temporal walk centrality (Oettershagen, Mutzel and Kriege, 2022): for every node the weighted number of temporal walks passing through it, where incoming walks are weighted by alpha and outgoing walks by beta per edge. Consecutive edges of a walk have strictly increasing time stamps. Runs in O(m + n) time.

References

• L. Oettershagen, P. Mutzel, and N. M. Kriege. Temporal walk centrality: ranking nodes in evolving networks. The Web Conference (WWW), 2022. DOI, arXiv

TemporalGraphStatistics

Basic statistics of a temporal graph, see get_statistics.

get_statistics(g::OrderedEdgeList)

Compute the basic statistics of g: numbers of nodes, temporal edges, static edges (ordered pairs (u, v) with an edge) and distinct time stamps (the lifetime) and transition times, their ranges, the ranges of the temporal in- and out-degrees, and the temporal graph parameters:

• the temporality, the largest number of distinct time stamps of a static edge (Mertzios, Michail and Spirakis, 2019);
• the largest number of temporal edges with the same time stamp;
• the vertex_interval_membership_width and the edge_interval_membership_width of the static edges.

References

• G. B. Mertzios, O. Michail, and P. G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 2019. DOI, arXiv

vertex_interval_membership_width(g::OrderedEdgeList)

The vertex-interval-membership width of g (Bumpus and Meeks, 2023): every node is active from the first to the last time stamp of its edges, and the width is the largest number of nodes active at the same time. Problems such as temporal Eulerian walks, NP-hard in general, are fixed-parameter tractable with respect to it. O(m + n log n) time.

References

• B. M. Bumpus and K. Meeks. Edge exploration of temporal graphs. Algorithmica 85, 2023. DOI, arXiv

edge_interval_membership_width(g::OrderedEdgeList; directed = true)

The edge-interval-membership width of g (Bumpus and Meeks, 2023): every static edge is active from its first to its last time stamp, and the width is the largest number of static edges active at the same time. The static edges are the ordered pairs (u, v) with an edge, or the unordered pairs if directed = false (for undirected graphs stored with both directions). See vertex_interval_membership_width.

is_simple(g::OrderedEdgeList; directed = true)

Whether the labeling of g is simple: every static edge has at most one distinct time stamp. The static edges are the ordered pairs (u, v), or the unordered pairs if directed = false (for undirected graphs stored with both directions, which then count once). Together with is_proper, directedness and strictness (positive transition times) these are the settings of temporal graphs compared by Casteigts, Corsini and Sarkar (2024).

References

• A. Casteigts, T. Corsini, and W. Sarkar. Simple, strict, proper, happy: a study of reachability in temporal graphs. Theoretical Computer Science 991, 2024. DOI, arXiv

is_proper(g::OrderedEdgeList; directed = true)

Whether the labeling of g is proper: adjacent static edges (static edges sharing a node) never have the same time stamp, i.e., every snapshot is a matching. The static edges are as in is_simple; with directed = true the edges (u, v, t) and (v, u, t) are adjacent, so undirected graphs stored with both directions need directed = false.

edge_burstiness(g::OrderedEdgeList, ti = time_interval(g))

Burstiness (σ - μ) / (σ + μ) of the inter-contact times of every static edge (u, v) with at least two contacts with time stamps in ti, where μ and σ are the mean and standard deviation. Returns a Dict from (u, v) to the burstiness.

node_burstiness(g::OrderedEdgeList, ti = time_interval(g))

Burstiness of the inter-contact times of the outgoing edges of every node with time stamps in ti (0 for nodes with fewer than two contacts).

temporal_clustering_coefficient(g::IncidentLists, s, ti = time_interval(g))

Temporal clustering coefficient of s: the number of temporal edges inside ti between the out-neighbors of s divided by k(k - 1) and by the length of ti, where k is the number of out-neighbors of s inside ti (0 if k < 2).

temporal_clustering_coefficient(g::IncidentLists, ti = time_interval(g))

Temporal clustering coefficient of all nodes.

topological_overlap(g::IncidentLists, s, ti = time_interval(g))

Average topological overlap of the out-neighborhoods of s at consecutive time stamps inside ti: the mean over consecutive pairs of neighborhoods (A, B) of |A ∩ B| / sqrt(|A| |B|). Returns 0 if s has edges at fewer than two time stamps.

topological_overlap(g::IncidentLists, ti = time_interval(g))

Topological overlap of all nodes.

kcores(edges, n = maximum node id)

Core numbers of the nodes 1:n of the undirected simple graph given by edges (anything with fields u and v, or tuples (u, v, ...)). Multiple edges, edge directions and self-loops are ignored. Computed with Graphs.core_number (O(m)).

temporal_khcores(g::OrderedEdgeList, h)

Core numbers of the (k, h)-cores (Wu et al., 2015): the core numbers of the static graph that connects two nodes iff they have at least h temporal contacts.

References

• H. Wu, J. Cheng, Y. Lu, Y. Ke, Y. Huang, D. Yan, and H. Wu. Core decomposition in large temporal graphs. IEEE International Conference on Big Data, 2015. DOI

temporal_lkcores(g::OrderedEdgeList, L, k)

Nodes of the largest (L, k)-lasting core (Hung and Tseng, 2021): a set of nodes that forms a k-core during L consecutive time stamps. For every window of L consecutive distinct time stamps the static graph of the node pairs that have a contact at each of the L time stamps is built, and the nodes with core number at least k of the window with the most such nodes are returned (sorted). The contact counts are updated incrementally while the window slides.

References

• W.-C. Hung and C.-Y. Tseng. Maximum (L, K)-lasting cores in temporal social networks. DASFAA, 2021. DOI

temporal_reachability(g::OrderedEdgeList, ti = time_interval(g))

Reachability matrix of g: R[s, v] is true iff there is a temporal path from s to v inside ti (every node reaches itself). Edges with transition time 0 can be chained at the same time stamp, as for the distances.

The sources are processed 64 at a time with bitsets, in one scan of the edges per block of sources: O(m n / 64) time instead of O(m n) for one search per source, and blocks are processed in parallel.

is_temporally_connected(g::OrderedEdgeList, ti = time_interval(g))

Whether every node of g reaches every other node by a temporal path inside ti.

earliest_arrival_matrix(g::OrderedEdgeList, ti = time_interval(g))

Earliest arrival times between all pairs of nodes: A[s, v] is the earliest arrival time at v of a temporal path from s inside ti, as returned by earliest_arrival_times(g, s, ti): typemax (printed as ∞) for unreachable nodes and 0 for v = s. Returned as a TemporalDistances matrix. Computed with the bitset scan of temporal_reachability, recording when every source first reaches every node: O(m n / 64 + n²) time and O(n²) memory.

temporal_flooding_time(g::OrderedEdgeList, s, ti = time_interval(g))

Time needed to flood g from s inside ti = (a, b): if s knows a piece of information at time a and every node forwards it on every edge it can use, the time from a until all nodes know it, i.e., the largest earliest arrival time from s minus a, or nothing if some node cannot be reached. This is the broadcast time of s in the flooding model (every informed node transmits on all its edges).

References

• A. E. F. Clementi, C. Macci, A. Monti, F. Pasquale, and R. Silvestri. Flooding time of edge-Markovian evolving graphs. SIAM Journal on Discrete Mathematics 24, 2010. DOI

temporal_flooding_times(g::OrderedEdgeList, ti = time_interval(g))

temporal_flooding_time of every node, from the earliest_arrival_matrix, as a TemporalDistances vector: typemax (printed as ∞) for the nodes that cannot flood g.

temporal_gossip_time(g::OrderedEdgeList, ti = time_interval(g))

Time needed for gossiping in g inside ti = (a, b): if every node knows its own piece of information at time a and all nodes forward everything they know on every edge, the time from a until every node knows every piece, i.e., the largest temporal_flooding_time, or nothing if g is not temporally connected inside ti. Equivalently, a plus the gossip time is the earliest t such that g restricted to (a, t) is temporally connected.

temporal_connected_components(g::OrderedEdgeList, ti = time_interval(g); unilateral = false)

The (open) temporal connected components of g: the maximal sets of nodes in which every node reaches every other node by a temporal path inside ti (Bhadra and Ferreira, 2003). The paths may leave the set. With unilateral = true, the maximal sets in which of every two nodes at least one reaches the other.

Unlike in static graphs the components can overlap: they are the maximal cliques of the graph joining the nodes that reach each other (Costa, Lopes, Marino and Silva, 2023), enumerated with the Bron–Kerbosch algorithm (exponential in the worst case; finding the largest component is NP-hard). Returns the components sorted by decreasing size.

References

• S. Bhadra and A. Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in wireless networks. ADHOC-NOW, 2003. DOI
• I. L. Costa, R. Lopes, A. Marino, and A. Silva. On computing large temporal (unilateral) connected components. Journal of Computer and System Sciences 144, 2024. DOI, arXiv

largest_temporal_connected_component(g::OrderedEdgeList, ti = time_interval(g);
                                     closed = false, unilateral = false)

A largest temporal connected component of g (see temporal_connected_components). With closed = true the paths between the nodes of the component must stay inside it, i.e., the temporal subgraph induced by the component is temporally connected.

Both problems are NP-hard (Bhadra and Ferreira, 2003), and so is deciding whether a set is a closed component (Costa et al., 2023). The open version is a maximum clique of the graph joining the nodes that reach each other, found exactly by branch and bound with coloring bounds (Tomita and Seki, 2003). The closed version is searched exactly by branching: if u cannot reach v inside a candidate set, one of them is removed; candidate sets are pruned with the same coloring bound. Both are exponential in the worst case.

References

• S. Bhadra and A. Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in wireless networks. ADHOC-NOW, 2003. DOI
• I. L. Costa, R. Lopes, A. Marino, and A. Silva. On computing large temporal (unilateral) connected components. Journal of Computer and System Sciences 144, 2024. DOI, arXiv
• E. Tomita and T. Seki. An efficient branch-and-bound algorithm for finding a maximum clique. DMTCS, 2003. DOI

source_component(g::OrderedEdgeList, S, ti = time_interval(g); closed = false)

The source component of the nodes S (a node or a collection of nodes): the largest set X of nodes such that every node of S reaches every node of X by a temporal path inside ti. With closed = true the paths must stay inside X (which then contains S, or is empty if the nodes of S cannot reach each other that way). For a single source this is the set of nodes reachable from it; with S equal to X the condition is temporal connectivity.

The union of two such sets is again one, so the component is unique: the open one is the intersection of the sets reachable from the nodes of S, the closed one the greatest fixed point of restricting this intersection to the subgraph induced by the current set (each step is a reachability computation).

References

• S. Bhadra and A. Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in wireless networks. ADHOC-NOW, 2003. DOI

sink_component(g::OrderedEdgeList, S, ti = time_interval(g); closed = false)

The sink component of the nodes S: the largest set X of nodes such that every node of X reaches every node of S by a temporal path inside ti (inside X with closed = true). See source_component.

window_components(g::OrderedEdgeList, ti = time_interval(g))

The window connected components of g for the time window ti = (a, b): the connected components of the static undirected graph of the edges with time stamps in [a, b]. Unlike temporal components they ignore the order of the edges. Returns the components sorted by decreasing size (isolated nodes are components of size 1).

persistent_components(g::OrderedEdgeList, ti = time_interval(g); resolution = nothing,
                      min_length = 1, min_size = 2)

The persistent connected components of g (Vernet, Pigné and Sanlaville, 2023): pairs (X, (t₁, t₂)) such that X is a connected component of every snapshot (the static graph of the edges with one time stamp) at the times t₁, t₁ + Δ, ..., t₂, with the interval as long as possible. Δ is the resolution of the time steps (by default the gcd of the time stamps minus the start of ti), so a component does not persist across an empty time step.

Returns the components with at least min_length steps and min_size nodes, as named tuples (nodes, interval, length) sorted by decreasing length and size. One sweep over the snapshots: O(L + m α(n)) time for L time steps.

References

• M. Vernet, Y. Pigné, and É. Sanlaville. A study of connectivity on dynamic graphs: computing persistent connected components. 4OR 21, 2023. DOI

interval_connected_components(g::OrderedEdgeList, T, ti = time_interval(g); resolution = nothing)

The T-interval connected components of g: the maximal sets of nodes X such that for every window of T consecutive time steps the graph of the edges present in all the snapshots of the window, restricted to X, is connected (Kuhn, Lynch and Oshman, 2010, for the whole graph; the component version is described in the Temporal Graph Wiki). Time steps are as in persistent_components. g is T-interval connected iff the result is the single set of all nodes.

The maximal sets connected in a family of graphs partition the nodes, and are computed by refining the partition {V} with the connected components of every window graph until nothing changes. Returns the components sorted by decreasing size.

References

• F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. STOC, 2010. DOI
• A. Casteigts, R. Klasing, Y. M. Neggaz, and J. G. Peters. Efficiently testing T-interval connectivity in dynamic graphs. CIAC, 2015. DOI

delta_temporal_connected_components(g::OrderedEdgeList, Δ, ti = time_interval(g);
                                    resolution = nothing, unilateral = false)

The Δ-temporal connected components of g (Temporal Graph Wiki): the maximal sets of nodes in which every node reaches every other node by a temporal path inside every time window (τ, τ + Δ) of ti = (a, b), with τ on the grid a, a + r, ... of the time steps (r is the resolution, as in persistent_components) and τ + Δ ≤ b; if Δ ≥ b - a the only window is ti and these are the temporal_connected_components. With unilateral = true, of every two nodes at least one must reach the other in every window. For integer times Δ is rounded down.

A window is only needed if it starts at a or at the first grid point after a time stamp: any other window contains all the edges of the last such window before it, hence all its paths. The components are the maximal cliques of the graph joining the nodes that reach each other in every window, enumerated with the Bron–Kerbosch algorithm as for the temporal connected components. O(K m n / 64) time for the reachability in the K ≤ m + 1 windows, plus the clique enumeration (exponential in the worst case). Returns the components sorted by decreasing size.

stream_components(g::OrderedEdgeList, ti = time_interval(g); gap = 0)

The connected components of g seen as a stream graph (Latapy, Viard and Magnien, 2018), whose elements are temporal nodes instead of nodes. Every edge (u, v, t, tt) inside ti is present during [t, t + tt], and so are its endpoints: a node is present while it has an edge, and its presence intervals at most gap apart are merged (it stays present in between). The temporal nodes are the pairs (v, (s, f)) of a node and a maximal presence interval, and an edge joins the temporal nodes of its endpoints that contain it. The order of time and the direction of the edges are ignored: a component is a set of temporal nodes linked by edges through time, e.g. a group of people that keeps meeting without long interruptions.

Returns the components (vectors of temporal nodes, sorted) sorted by decreasing number of temporal nodes; nodes without edges inside ti belong to none. O(m log m) time.

References

• M. Latapy, T. Viard, and C. Magnien. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining 8, 2018. DOI, arXiv

reachability_dominating_set(g::OrderedEdgeList, ti = time_interval(g); exact = false)

A small temporal reachability dominating set (TaRDiS) of g (Kutner and Larios-Jones, 2026): a set S of nodes such that every node is in S or is reached from a node of S by a temporal path inside ti. If the nodes of S are infected at the start of ti and every contact transmits, every node gets infected.

Finding a smallest one is NP-hard (it is a set cover problem on the rows of the temporal_reachability matrix). By default the greedy algorithm repeatedly chooses the node that reaches the most nodes not reached yet, which is at most ln n + 1 times larger than optimal (Chvátal, 1979). With exact = true a smallest set is found by branch and bound from the greedy solution (exponential in the worst case). Returns the nodes of the set, sorted.

References

• D. C. Kutner and L. Larios-Jones. Temporal reachability dominating sets: contagion in temporal graphs. Journal of Computer and System Sciences 155, 2026. DOI, arXiv
• V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(3), 1979. DOI

max_reach_seeds(g::OrderedEdgeList, k, ti = time_interval(g); exact = false)

At most k nodes that together reach the most nodes of g by temporal paths inside ti: influence maximization (Kempe, Kleinberg and Tardos, 2003) in the deterministic model where the seeds are informed at the start of ti and every contact transmits. Returns (seeds, reached): the seeds, sorted, and the number of nodes they reach (including themselves). Fewer than k seeds are returned only if they reach all nodes.

The problem is NP-hard (maximum coverage on the rows of the temporal_reachability matrix). By default the greedy algorithm, with lazy evaluation of the gains, reaches at least 1 - 1/e ≈ 63% of the optimum (Nemhauser, Wolsey and Fisher, 1978); with exact = true an optimal set is found by branch and bound (exponential in the worst case).

References

• D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. KDD, 2003. DOI
• G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming 14, 1978. DOI

vertex_expansion(g::OrderedEdgeList, ti = time_interval(g); compressed = true)

The vertex expansion (time-expanded graph) of g inside ti, as a Graphs.SimpleDiGraph: a node for every pair (v, τ) of a node and a time, an arc (v, τ) → (v, τ') between consecutive times of v (waiting) and an arc (u, t) → (v, t + tt) for every temporal edge (traversal). Temporal walks of g are exactly the directed walks of the expansion, so v is reachable from u iff some copy of v is reachable from the first copy of u.

With compressed = true a node has copies only at the times at which an edge leaves or reaches it (O(n + m) nodes and arcs, as used for flows); with compressed = false every node has a copy at every such time of the whole graph (n L nodes for L distinct times, the classical layered expansion).

Returns (graph, nodes) where nodes[i] = (v, τ) is the pair of expansion node i.

References

• H. Wu, J. Cheng, Y. Ke, S. Huang, Y. Huang, and H. Wu. Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering 28(11), 2016. DOI
• E. C. Akrida, J. Czyzowicz, L. Gąsieniec, Ł. Kuszner, and P. G. Spirakis. Temporal flows in temporal networks. Journal of Computer and System Sciences 103, 2019. DOI, arXiv

edge_expansion(g::OrderedEdgeList, ti = time_interval(g); β = Inf, hubs = false)

The edge expansion (temporal line graph) of g inside ti, as a Graphs.SimpleDiGraph: a node for every temporal edge and an arc e → f whenever f can follow e, i.e., f leaves the head of e at time arr(e) = e.t + e.tt or later (and at most arr(e) + β with a waiting constraint). Directed walks of the expansion are exactly the temporal walks (β-restless walks) of g.

The expansion can have Θ(m²) arcs. With hubs = true (only without waiting constraint) one extra hub node per departure time (v, τ) is used instead: hubs of a node are chained by increasing time, an edge points to the first hub of its head at or after its arrival and a hub to the edges leaving at its time, which gives O(m) arcs with the same reachability between edge nodes.

Returns (graph, edges, hubs): node i ≤ length(edges) is the temporal edge edges(g)[edges[i]], the following nodes are the hubs hubs[j] = (v, τ).

restless_path(g::OrderedEdgeList, s, z, β, ti = time_interval(g))

A β-restless temporal path from s to z (Casteigts, Himmel, Molter and Zschoche, 2021): a temporal path that visits every node at most once and waits at most β at every intermediate node, i.e., every edge departs in [a, a + β] where a is the arrival time of the previous edge (the departure from s is free). Returns the edges of a path, or nothing if there is none.

Unlike restless walks (see temporal_distances with β), finding a restless path is NP-hard for every β ≥ 1, so this is an exact exponential-time search: a depth-first search over the edges, pruned by checking that z is still reachable by a restless walk avoiding the visited nodes (a polynomial relaxation). It is fast when restless walks rarely revisit nodes.

References

• A. Casteigts, A.-S. Himmel, H. Molter, and P. Zschoche. Finding temporal paths under waiting time constraints. Algorithmica 83(9), 2021. DOI, arXiv

temporal_max_flow(g::OrderedEdgeList, s, z, ti = time_interval(g);
                  capacity = nothing, buffers = nothing, β = Inf)

Maximum temporal flow from s to z inside ti (Akrida, Czyzowicz, Gąsieniec, Kuszner and Spirakis, 2019): the largest amount that can be sent from s to z when temporal edge i carries at most capacity[i] (1 by default) at its time and nodes can store any amount between edges (at most buffers[v] at node v if given; s and z always have unbounded storage). With a waiting constraint β, the flow follows β-restless walks instead (nothing can be stored for longer than β).

Returns (value, flow) where flow[i] is the amount on edge i of edges(g). With the default unit capacities the value is the maximum number of edge-disjoint temporal paths (see temporal_edge_disjoint_paths). Computed as a static maximum flow (Dinic's algorithm) in the time-expanded network, of size O(n + m) (O(Σ_v deg⁻(v) deg⁺(v)) with β).

References

• E. C. Akrida, J. Czyzowicz, L. Gąsieniec, Ł. Kuszner, and P. G. Spirakis. Temporal flows in temporal networks. Journal of Computer and System Sciences 103, 2019. DOI, arXiv

temporal_min_cut(g::OrderedEdgeList, s, z, ti = time_interval(g); capacity = nothing, β = Inf)

A minimum temporal cut between s and z: a set of temporal edges of minimum total capacity (number of edges by default) whose removal leaves no temporal path from s to z inside ti (no β-restless walk with a waiting constraint). Its capacity equals the temporal_max_flow (Akrida et al., 2019, Theorem 1; Berman, 1996). Returns (value, edges) with the indices of the cut edges in edges(g).

References

• E. C. Akrida, J. Czyzowicz, L. Gąsieniec, Ł. Kuszner, and P. G. Spirakis. Temporal flows in temporal networks. Journal of Computer and System Sciences 103, 2019. DOI, arXiv
• K. A. Berman. Vulnerability of scheduled networks and a generalization of Menger's theorem. Networks 28(3), 1996. DOI

temporal_edge_disjoint_paths(g::OrderedEdgeList, s, z, ti = time_interval(g); β = Inf)

A maximum set of edge-disjoint temporal paths from s to z inside ti, as vectors of edges. Their number equals the minimum number of temporal edges whose removal disconnects z from s (temporal_min_cut): Menger's theorem holds for edge-disjoint temporal paths (Berman, 1996), unlike for vertex-disjoint ones (Kempe, Kleinberg and Kumar, 2000). With a waiting constraint β the result are edge-disjoint β-restless walks (which may visit a node several times).

References

• K. A. Berman. Vulnerability of scheduled networks and a generalization of Menger's theorem. Networks 28(3), 1996. DOI
• D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences 64(4), 2002. DOI

temporal_out_disjoint_paths(g::OrderedEdgeList, s, z, ti = time_interval(g))

A maximum set of out-disjoint temporal paths from s to z inside ti: no two of them leave the same node at the same time. Their number equals the minimum number of node departure times (v, t) whose removal (deleting all the edges leaving v at time t) disconnects z from s (Mertzios, Michail and Spirakis, 2019, Theorem 3). Computed as a maximum flow with one unit-capacity node per departure time.

References

• G. B. Mertzios, O. Michail, and P. G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 2019. DOI, arXiv

temporal_vertex_separator(g::OrderedEdgeList, s, z, ti = time_interval(g))

A minimum temporal (s, z)-separator: a smallest set of nodes other than s and z whose removal leaves no temporal path from s to z inside ti, or nothing if an edge goes directly from s to z. Strict and non-strict paths correspond to positive and zero transition times.

Finding a minimum separator is NP-hard (Kempe, Kleinberg and Kumar, 2000; Zschoche, Fluschnik, Molter and Niedermeier, 2020), and the minimum can exceed the maximum number of vertex-disjoint paths. This exact algorithm is a bounded search tree: a separator must contain an inner node of every path, so it branches on the inner nodes of a minimum hop path, for increasing sizes k starting from the number of vertex-disjoint paths found greedily. It runs in O(ℓ^k m) time, where ℓ is the largest number of hops of the paths, which is fixed-parameter tractable in k and the number of time stamps for strict paths.

References

• D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences 64(4), 2002. DOI
• P. Zschoche, T. Fluschnik, H. Molter, and R. Niedermeier. The complexity of finding small separators in temporal graphs. Journal of Computer and System Sciences 107, 2020. DOI, arXiv

earliest_arrival_tree(g::OrderedEdgeList, r, ti = time_interval(g))

A temporal spanning tree of the nodes reachable from r inside ti in which every node is reached at its earliest arrival time: MST_a of Huang, Fu and Liu (2015). Returns the tree edges, one entering every reachable node other than r, sorted by time. Computed in O(m) time (after sorting the edges of every node) with the stack-based algorithm of the paper, which is correct also for transition times 0.

References

• S. Huang, A. W.-C. Fu, and R. Liu. Minimum spanning trees in temporal graphs. SIGMOD, 2015. DOI

minimum_weight_spanning_tree(g::OrderedEdgeList, r, ti = time_interval(g);
                             weights = nothing, level = 2)

An approximate MST_w of Huang, Fu and Liu (2015): a temporal spanning tree of the nodes reachable from r inside ti (one incoming edge per node, every tree path a temporal path) of small total weight, where edge i weighs weights[i] (its transition time by default). Returns (edges, weight).

Finding a minimum weight tree is NP-hard and MAX-SNP-hard. The algorithm of the paper transforms the graph into an instance of the Directed Steiner Tree problem (one copy of every node per arrival time) and solves it with the level-level greedy algorithm of Charikar et al. (1999), with the improvements of the paper (density bounds); the approximation ratio is $i^2 (i-1) k^{1/i}$ for level $i ≥ 2$ and $k$ terminals. level = 1 connects every node by a cheapest temporal path. Levels 1 and 2 are supported; level 2 takes O(n m log m) time for the shortest paths plus the greedy steps.

References

• S. Huang, A. W.-C. Fu, and R. Liu. Minimum spanning trees in temporal graphs. SIGMOD, 2015. DOI
• M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li. Approximation algorithms for directed Steiner problems. Journal of Algorithms 33(1), 1999. DOI

temporal_spanner(g::OrderedEdgeList, ti = time_interval(g); minimal = false)

A temporal spanner of g: a subset of the edges inside ti with the same reachability between all pairs of nodes. It is the union of an earliest arrival tree (see earliest_arrival_tree) from every node, with at most n (n - 1) edges, computed in O(n m) time. With minimal = true edges are then removed one at a time as long as the reachability does not change (O(k m n / 64) time for k edges of the union), so that the result is inclusion-minimal.

Minimum spanners are NP-hard to compute and to approximate (Axiotis and Fotakis, 2016), and some temporally connected graphs need Ω(n²) edges; for temporal cliques see temporal_clique_spanner.

References

• K. Axiotis and D. Fotakis. On the size and the approximability of minimum temporally connected subgraphs. ICALP, 2016. DOI, arXiv

temporal_clique_spanner(g::OrderedEdgeList)

A temporal spanner with O(n log n) edges of a temporal clique: an undirected temporal graph with exactly one time label on every pair of nodes, given with both directions of every edge (or one of them) and transition time 0 (non-strict paths). Casteigts, Peters and Schoeters (2021) proved that such spanners always exist; this is the simpler algorithm of Angrick et al. (ESA 2024): the clique is reduced to a bipartite clique, nodes are removed when they can delegate their journeys to another node ("dismountability"), and the remaining instance is split in halves recursively. Returns the edges of the spanner (both directions of every chosen pair), in O(n²) time per level of the recursion.

References

• A. Casteigts, J. G. Peters, and J. Schoeters. Temporal cliques admit sparse spanners. Journal of Computer and System Sciences 121, 2021. DOI, arXiv
• S. Angrick, B. Bals, T. Friedrich, H. Gawendowicz, N. Hastrich, N. Klodt, P. Lenzner, J. Schmidt, G. Skretas, and A. Wells. How to reduce temporal cliques to find sparse spanners. ESA, 2024. DOI, arXiv

augmented_event_graph(g::OrderedEdgeList, ti = time_interval(g); β = Inf)

The augmented event graph of g (Heeg, Sauer, Mutzel and Scholtes, 2025): the temporal event graph (the edge_expansion, with a node per temporal edge and an arc e → f when f can follow e within the waiting time β), augmented with the nodes of g and the arcs u → e and e → v for every temporal edge e = (u, v, t, tt). Its paths are the time-respecting paths of g, so two temporal graphs have the same time-respecting paths up to renaming iff their augmented event graphs are isomorphic.

Returns (graph, labels, edges): graph is a Graphs.SimpleDiGraph whose nodes 1:n are the nodes of g (label 0) and whose node n + i is the temporal edge edges(g)[edges[i]] (label 1). The paper uses unit transition times and a maximum time difference δ between consecutive edges; this is tt = 1 and β = δ - 1.

References

• F. Heeg, J. Sauer, P. Mutzel, and I. Scholtes. Weisfeiler and Leman follow the arrow of time: expressive power of message passing in temporal event graphs. 2025. arXiv

temporal_isomorphism(g1::OrderedEdgeList, g2::OrderedEdgeList; kind = :event, β = Inf,
                     ti1 = time_interval(g1), ti2 = time_interval(g2))

An isomorphism between the temporal graphs g1 and g2 of the given kind (Heeg, Sauer, Mutzel and Scholtes, 2025), or nothing if there is none:

• :event — time-respecting path isomorphism (equivalently, consistent event graph isomorphism): bijections of the nodes and of the temporal edges that map every temporal edge (u, v, t) to an edge between the images of u and v and preserve all time-respecting paths with waiting time at most β. Timestamps may change as long as the time-respecting paths do not. Computed as an isomorphism of the augmented_event_graphs (Theorem 1 of the paper). Returns (nodes, edges): node v of g1 maps to nodes[v], and edge i of edges(g1) to edge edges[i] of edges(g2) (0 for edges outside the time interval).
• :aggregated — time-aggregated isomorphism: the static graphs with the number of temporal edges of every pair of nodes are isomorphic. Returns (nodes,).
• :concatenated — time-concatenated isomorphism (timewise isomorphism of Wałęga and Rawson): the static graphs with the sets of timestamps relative to the first one are isomorphic. Returns (nodes,).

Time-concatenated isomorphic graphs are event isomorphic, and event isomorphic graphs are time-aggregated isomorphic (Theorem 2). Graph isomorphism has no known polynomial algorithm; this exact test refines the colors of both graphs together with the directed Weisfeiler–Leman algorithm and individualizes nodes when the refinement stops, which is fast unless the graphs are very symmetric.

References

• F. Heeg, J. Sauer, P. Mutzel, and I. Scholtes. Weisfeiler and Leman follow the arrow of time: expressive power of message passing in temporal event graphs. 2025. arXiv
• P. A. Wałęga and M. Rawson. Expressive power of temporal message passing. AAAI, 2025. DOI

is_temporally_isomorphic(g1::OrderedEdgeList, g2::OrderedEdgeList; kind = :event, β = Inf)

Whether temporal_isomorphism finds an isomorphism of the given kind.

temporal_wl_equivalent(g1::OrderedEdgeList, g2::OrderedEdgeList; β = Inf, kind = :event)

The temporal Weisfeiler–Leman test of Heeg, Sauer, Mutzel and Scholtes (2025): run the directed Weisfeiler–Leman color refinement (D-WL) on the augmented_event_graphs of both graphs until the colors are stable and compare the color histograms. It is a one-sided test: false proves that the graphs are not time-respecting path isomorphic, true means that D-WL (and message passing neural networks on the augmented event graph) cannot distinguish them. With kind = :aggregated or :concatenated the refinement runs on the corresponding labeled static graphs. Runs in O(n + a) time per round (plus sorting the colors) for a arcs; neighbor multisets are compared through 64-bit hashes, so a collision (of negligible probability) could only make the test weaker.

References

• F. Heeg, J. Sauer, P. Mutzel, and I. Scholtes. Weisfeiler and Leman follow the arrow of time: expressive power of message passing in temporal event graphs. 2025. arXiv
• E. Rossi, B. Charpentier, F. Di Giovanni, F. Frasca, S. Günnemann, and M. M. Bronstein. Edge directionality improves learning on heterophilic graphs. Learning on Graphs Conference (LoG), 2023. PMLR

temporal_wl_kernel(graphs; iterations = 3, β = Inf, augmented = true)

The Weisfeiler–Leman subtree kernel of a collection of temporal graphs on their augmented_event_graphs (Heeg, Sauer, Mutzel and Scholtes, 2025): every graph is represented by the numbers of nodes of every color after 0, 1, …, iterations rounds of directed color refinement, with colors shared by all graphs, and K[i, j] is the dot product of these vectors. With augmented = false the refinement runs on the temporal event graphs alone, as in the temporal graph kernel of Oettershagen, Kriege, Morris and Mutzel (2020), which ignores which nodes the temporal edges join. Returns (kernel, features) where features[i] maps colors to counts.

References

• F. Heeg, J. Sauer, P. Mutzel, and I. Scholtes. Weisfeiler and Leman follow the arrow of time: expressive power of message passing in temporal event graphs. 2025. arXiv
• L. Oettershagen, N. M. Kriege, C. Morris, and P. Mutzel. Temporal graph kernels for classifying dissemination processes. SDM, 2020. DOI, arXiv

augmented_event_gnngraph(g::OrderedEdgeList, ti = time_interval(g); β = Inf)

The augmented_event_graph of g as a GNNGraph of GNNGraphs.jl, with node data label (0 for the nodes of g, 1 for its temporal edges) and x, the one-hot encoding of the labels: the input of the event graph neural network of Heeg, Sauer, Mutzel and Scholtes (2025), e.g. a directed GNN of GraphNeuralNetworks.jl. Available after using GNNGraphs (or GraphNeuralNetworks).

temporal_motif_counts(g::OrderedEdgeList, δ; strict = true)

Numbers of instances of all δ-temporal motifs with 3 edges on 2 or 3 nodes (Paranjape, Benson and Leskovec, WSDM 2017), as a 6×6 matrix M: M[i, j] counts the motif $M_{i,j}$ of Figure 3 of the paper, in the same layout as the SNAP implementation. If the first edge of the motif is $a → b$ and $c$ is the third node, column j is given by the third edge and row i by the second edge:

so that M[5:6, 1:2] are the 2-node motifs, M[1:2, 3:4] and M[3:4, 5:6] the triangles and the others the stars.

An instance is a sequence of three edges e₁, e₂, e₃ of g with t₃ - t₁ ≤ δ that maps onto the motif. With strict = true the time stamps must increase strictly (the definition of the paper); with strict = false edges with equal time stamps are ordered as in edges(g). Only departure times are used and self loops are ignored.

Stars and 2-node motifs are counted in O(m) time with one sweep over the edges of each node, and triangles in O(m √τ) time (τ triangles in the static graph) with one sweep per pair of nodes, as in the paper; nodes and pairs are processed in parallel.

References

• A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. WSDM, 2017. DOI, arXiv

temporal_motif_count(g::OrderedEdgeList, motif, δ; strict = true)

Number of instances of the δ-temporal motif motif (Paranjape, Benson and Leskovec, 2017), given as a vector of directed edges (x, y) on the nodes 1:k, in their temporal order: for example [(1, 2), (2, 3), (3, 1)] is a cyclic triangle and [(1, 2), (2, 1), (1, 2), (2, 1)] a 4-edge exchange between two nodes. The static graph of the motif must be connected. Instances and strict are as in temporal_motif_counts.

This is the general algorithm of the paper: it enumerates the embeddings of the static graph of the motif in the static graph of g and counts the matching subsequences of their edges with a sliding window, in O(l² m') time per embedding (l motif edges, m' temporal edges on the embedding). The embeddings are enumerated in parallel. It works for any motif but can be slow for motifs with high-degree centers; use temporal_motif_counts for the motifs with 3 edges.

References

• A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. WSDM, 2017. DOI, arXiv

randomize(g::OrderedEdgeList, models::ReferenceModel...; rng = Random.default_rng())

A random temporal network drawn from the microcanonical randomized reference model model applied to g (Gauvin et al., SIAM Review 2022). With several models they are applied in sequence: randomize(g, A, B) is the composition of A followed by B. A link shuffling followed by a timeline shuffling, or a sequence shuffling followed by a snapshot shuffling, is again a microcanonical model (Propositions V.5 and V.6 of the paper), e.g. randomize(g, TopologyLinkShuffling(), TimestampShuffling()) is $P[\mathcal{L}, p(\mathbf{w}), \mathbf{t}]$.

Links are ordered pairs of nodes; for undirected networks store every contact once and pass directed = false to the models (then use make_undirected on the result if needed). The result has the same nodes and time interval as g.

References

• L. Gauvin, M. Génois, M. Karsai, M. Kivelä, T. Takaguchi, E. Valdano, and C. L. Vestergaard. Randomized reference models for temporal networks. SIAM Review 64(4), 2022. DOI, arXiv

reference_samples(f, g::OrderedEdgeList, models::ReferenceModel...; samples = 100,
                  rng = Random.default_rng())

The values f(h) for samples independent random networks h = randomize(g, models...), computed in parallel (each sample has its own random number generator seeded from rng, so the result is reproducible). Comparing f(g) with these values tells how much of f is explained by the features kept by the model, e.g. the z-scores of motif counts:

null = reference_samples(h -> temporal_motif_counts(h, 3600), g, TimestampShuffling(); samples = 100)
z = (temporal_motif_counts(g, 3600) .- mean(null)) ./ std(null)

ReferenceModel

Supertype of the randomized reference models of temporal networks, see randomize.

LinkShuffling(; directed = true)

$P[p_\mathcal{L}(Θ)]$, link shuffling: the static graph is replaced by a uniformly random graph with the same number of links (Erdős–Rényi), and the timelines are redistributed at random on the new links. Keeps the multiset of timelines (hence the activity timeline and the inter-event times on links); randomizes the topology.

DegreeLinkShuffling(; directed = true, swaps = 10)

$P[\mathbf{k}, p_\mathcal{L}(Θ)]$, degree-constrained link shuffling: the static graph is randomized keeping the degree of every node (in- and out-degrees if directed), with swaps double edge swaps per link (Maslov and Sneppen), and the timelines are redistributed at random on the links.

References

• S. Maslov and K. Sneppen. Specificity and stability in topology of protein networks. Science 296(5569), 2002. DOI, arXiv

TopologyLinkShuffling(; directed = true)

$P[\mathcal{L}, p_\mathcal{L}(Θ)]$, topology-constrained link shuffling: the timelines are permuted at random among the links of the static graph, which is kept. Destroys the correlations between topology and dynamics.

WeightLinkShuffling(; directed = true)

$P[\mathbf{w}, p_\mathcal{L}(Θ)]$, weight-constrained link shuffling: the timelines are permuted at random among the links with the same number of events.

RandomTimes(; directed = true, resolution = nothing)

$P[\mathbf{w}]$, weight-constrained timeline shuffling (also called random times or Poissonized inter-event intervals): every event gets a uniformly random start time in the observation interval, keeping its link; the events of a link have distinct times. Keeps the static graph and the number of events of every link.

InterEventShuffling(; directed = true)

$P[π_\mathcal{L}(Δτ), \mathbf{t}_1]$, inter-event shuffling: on every link the intervals between the start times of consecutive events are permuted at random, keeping the time of the first event. Keeps the static graph, the number of events and the distribution of inter-event times of every link; destroys their order (e.g. bursts). The durations keep their order on the link.

TimelineShifting(; directed = true, resolution = nothing)

$P[\mathrm{per}(Θ)]$, timeline shifting: every timeline is translated by a uniformly random offset with periodic boundary conditions on the observation interval. Keeps all intervals between the events of a link, randomizes the relative timing of the links.

TimestampShuffling(; simple = false, swaps = 10)

$P[\mathbf{w}, \mathbf{t}]$, timestamp shuffling (also called permuted times or time reshuffle): the start times (with the durations) are permuted at random among all events, keeping their links. Keeps the static graph, the number of events of every link and the activity timeline (the number of events at every time).

A random permutation, as in the literature, can give a link two events with the same time; such networks are then less likely than the others. With simple = true the times are instead exchanged between random pairs of events, swaps times per event, rejecting the exchanges that would repeat an event. No repeated event is created (those of the input disappear as their times are exchanged), and the result is uniform among the networks without repeated events.

SequenceShuffling(; active = true, resolution = nothing)

$P[p_\mathcal{T}(Γ), χ_{\mathbb{N}^+}(\mathbf{A})]$, activity-constrained sequence shuffling: the snapshots (events with the same start time) are permuted at random among the times with at least one event. With active = false, $P[p_\mathcal{T}(Γ)]$: the snapshots are placed at distinct random times of the time grid of the observation interval. Keeps every snapshot, destroys the temporal order.

SnapshotShuffling(; directed = true)

$P[\mathbf{t}]$, snapshot shuffling: every snapshot is replaced by a uniformly random graph with the same number of events (distinct pairs of distinct nodes). Keeps the times of all events; randomizes the topology.

DegreeSnapshotShuffling(; directed = true, swaps = 10)

$P[\mathbf{d}]$, degree-constrained snapshot shuffling: every snapshot is randomized keeping the instantaneous degree of every node (in- and out-degrees if directed), with swaps double edge swaps per event.

References

• S. Maslov and K. Sneppen. Specificity and stability in topology of protein networks. Science 296(5569), 2002. DOI, arXiv

IsomorphicSnapshotShuffling()

$P[\mathrm{iso}(Γ)]$, isomorphic snapshot shuffling: the node ids of every snapshot are permuted at random, independently for every snapshot. Keeps the structure of every snapshot up to isomorphism.

EventShuffling(; directed = true, resolution = nothing)

$P[p(τ)]$ ($P[E]$ for instantaneous events), event shuffling: every event gets a uniformly random pair of distinct nodes and a uniformly random start time, keeping its duration; all events are distinct. The most random model: it keeps only the nodes, the observation interval, the number of events and their durations.

random_temporal_graph(n, p, T; directed = false, transition_time = 1,
                      rng = Random.default_rng())

A random temporal graph with n nodes whose snapshots at the times 1, ..., T are independent Erdős–Rényi graphs: every pair of distinct nodes (ordered pair if directed) has an edge at every time with probability p, independently. Undirected edges are stored in both directions. The default transition time 1 gives strict paths (at most one edge per snapshot); use transition_time = 0 for non-strict paths.

The pairs are drawn by geometric jumps, in O(nT + m) expected time for m edges. The time interval is (1, T + transition_time).

random_simple_temporal_graph(n, p; directed = false, rng = Random.default_rng())

A random simple temporal graph (Casteigts, Raskin, Renken and Zamaraev, 2024): an Erdős–Rényi graph G(n, p) (directed if directed) whose m edges get the times 1, ..., m in uniformly random order, one per edge. The labeling is simple (one time per edge) and proper (adjacent edges have different times), so the temporal paths are the paths with increasing times; transition times are 1. With p = 1 this is a random temporal clique.

Casteigts et al. show sharp thresholds for temporal connectivity at p = log n / n (some node reaches all others) and p = 3 log n / n (all pairs reach each other).

References

• A. Casteigts, M. Raskin, M. Renken, and V. Zamaraev. Sharp thresholds in random simple temporal graphs. SIAM Journal on Computing, 2024. DOI, arXiv

random_temporal_labeling(G::Graphs.AbstractGraph, T; labels = 1, transition_time = 1,
                         rng = Random.default_rng())

The temporal graph of the static graph G in which every edge gets labels distinct times drawn uniformly at random from 1, ..., T, in both directions if G is undirected. Together with the generators of Graphs.jl it gives random temporal paths, stars, trees, grids and cliques, e.g. random_temporal_labeling(Graphs.star_graph(10), 5) or, for a random spanning tree with random times, random_temporal_labeling(Graphs.uniform_tree(n), T). With labels = 1 the result is simple (one time per edge). The time interval is (1, T + transition_time).

round_robin_temporal_clique(n)

The round-robin temporal clique on n nodes: the undirected complete graph whose edges are scheduled by the circle method of round-robin tournaments. Round r (time r) is a matching, and every pair of nodes meets exactly once, in n - 1 rounds for even n and n rounds for odd n (one node rests in each round). The labeling is simple and proper; transition times are 1.

temporal_hypercube(d)

The d-dimensional hypercube on 2^d nodes whose edges along dimension k have time k (k = 1, ..., d), undirected, with transition times 1. Every pair of nodes is joined by exactly one temporal path (fix the differing bits in increasing order), so the graph is temporally connected and every one of its d 2^(d-1) edges is needed: no temporal spanner is smaller (Kempe, Kleinberg and Kumar, 2002). Node x + 1 is the bit string x.

References

• D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences 64(4), 2002. DOI

temporal_knodel_graph(d)

The Knödel graph W(d, 2^d) on 2^d nodes with the edges of dimension k at time k (k = 1, ..., d), undirected, with transition times 1. Nodes j + 1 and 2^(d-1) + j + 1 form the two sides j = 0, ..., 2^(d-1) - 1; dimension k joins j on the first side to j + 2^(k-1) - 1 (mod 2^(d-1)) on the second. If in round k every node exchanges what it knows along dimension k, all nodes know everything after d rounds, the minimum possible for 2^d nodes (Knödel, 1975). So the graph is temporally connected; its labeling is proper, and since the knowledge of every node doubles in every round, every pair of nodes is joined by exactly one temporal path and every edge is needed.

References

• W. Knödel. New gossips and telephones. Discrete Mathematics 13(1), 1975. DOI
• G. Fertin and A. Raspaud. A survey on Knödel graphs. Discrete Applied Mathematics 137(2), 2004. DOI

TemporalDataset

Metadata of a dataset of the catalog returned by temporal_datasets: name, source, url, description, whether its edges are directed, its license and the citation requested by the authors.

temporal_datasets()

The catalog of public temporal network datasets that load_dataset can download: SNAP temporal networks (messages, e-mails, Stack Exchange interactions, Wikipedia talk pages, Bitcoin trust networks) and SocioPatterns face-to-face contact networks. Every entry is a TemporalDataset with its source, license and the paper to cite.

load_dataset(name; dir = dataset_dir(), directed = nothing, transition_time = 1,
             node_type = Int32)

Load the temporal network name of the catalog temporal_datasets as an OrderedEdgeList, downloading it from its original source on first use (the license and the paper to cite are printed then) and caching it in dir. Node ids are renumbered 1:n; original_ids gives the ids of the source. Every edge gets the transition time transition_time. SocioPatterns contacts are undirected and loaded in both directions unless directed = true.

g = load_dataset("CollegeMsg")
h = load_dataset("sp-workplace-2015")   # face-to-face contacts, 20 s resolution

dataset_dir()

The directory where load_dataset caches the downloaded files: the environment variable TEMPORALGRAPHS_DATA if set, otherwise a directory inside the first Julia depot.