Graph representations

All representations are parametric in the node id type V and the time type T and store their data in a few contiguous vectors.

Convert between them with to_incident_lists, to_ordered_edge_list, to_trs_graph and to_directed_line_graph. Distances work on the first three representations with the same functions (except the latest departure times, which are not implemented for TRSGraph):

julia> using TemporalGraphs

julia> g = OrderedEdgeList(3, [(1, 2, 1, 1), (2, 3, 4, 1), (1, 3, 6, 1)]);

julia> il = to_incident_lists(g); trs = to_trs_graph(g);

julia> minimum_durations(g, 1) == minimum_durations(il, 1) == minimum_durations(trs, 1)
true

julia> out_edges(il, 1)
2-element view(::Vector{TemporalEdge{Int32, Int64}}, 1:2) with eltype TemporalEdge{Int32, Int64}:
 (1 2 1 1)
 (1 3 6 1)

Edge stream

OrderedEdgeList keeps the edges sorted by time in one vector: by (t, tt, u, v), or in the given order if they were already sorted by time (with the edges of transition time 0 first at every time stamp). The nodes are 1:n at every time (see Nodes over time). It also stores the ids that the nodes had in the input file (original_id, node_map). This is the representation returned by the loaders.

Incident lists

IncidentLists groups the edges by tail in compressed sparse row format: out_edges(g, u) is a view of a contiguous block of the edge vector, sorted by time, so the edges leaving u after a given time are found by binary search.

Time-respecting static graph

A TRSGraph has one time-node (v, τ) for each time τ at which v has an outgoing edge, plus one for the latest arrival at v. Consecutive time-nodes of the same node are linked by waiting edges; a temporal edge (u, v, t, tt) links (u, t) to the first time-node of v not before t + tt. Use num_trs_nodes, trs_node, trs_time and trs_neighbors to inspect it.

Directed line graph

The DirectedLineGraph has one node per temporal edge and an edge from e to f whenever f can follow e in a temporal path. It can be much larger than the temporal graph.

Snapshot graphs

A discrete-time temporal graph is often given, or best analyzed, as a sequence of static snapshot graphs, one per time step.

• snapshots cuts the time interval into steps of length resolution. Each step becomes a Graphs.jl graph of the edges whose time stamp falls in it. By default the step is the resolution of the time stamps, the greatest common divisor of t - a over all edges, where a is the start of the time interval, so every time stamp has its own snapshot.
• OrderedEdgeList(graphs, times) converts a sequence of snapshots back into a temporal graph. Undirected snapshots give both directions. With transition_time = 1 and consecutive times the paths are strict, using at most one edge per snapshot; with transition_time = 0 they are non-strict.
• aggregate_time reduces the time resolution, for example from seconds to hours, by moving every edge to the start of its step.
• static_graph(g, ti) returns the unweighted static graph of the edges in a time window, as a Graphs.jl SimpleDiGraph (SimpleGraph with directed = false).

julia> using TemporalGraphs, Graphs

julia> g = OrderedEdgeList(3, [(1, 2, 0, 1), (2, 3, 0, 1), (1, 3, 5, 1), (2, 1, 7, 1)]);

julia> S = snapshots(g; resolution = 5);

julia> S.times, ne.(S.graphs)
([0, 5], [2, 2])

julia> edges(OrderedEdgeList(S.graphs, S.times; transition_time = 5))
4-element Vector{TemporalEdge{Int32, Int64}}:
 (1 2 0 5)
 (2 3 0 5)
 (1 3 5 5)
 (2 1 5 5)

julia> edges(aggregate_time(g, 5))   # the edge at time 7 moves to the step starting at 5
4-element Vector{TemporalEdge{Int32, Int64}}:
 (1 2 0 1)
 (2 3 0 1)
 (1 3 5 1)
 (2 1 5 1)

The snapshot-based measures of the package (persistent_components, interval_connected_components, window_components and the snapshot shufflings of randomize) use the same time steps.

Transformations

• normalize_graph: remove identical edges (and self-loops).
• make_undirected: add the reverse of every edge.
• scale_timestamps, unit_transition_times.
• reverse(g, ti): the temporal transpose, which turns paths from u to w into paths from w to u with the same duration.
• to_aggregated_edge_list: the static graph with contact counts (see static_graph above for the unweighted one).

Graphs.jl

The package extends Graphs.edges, Graphs.nv and Graphs.ne for its graph types, so using Graphs, TemporalGraphs does not cause name clashes.