A Unifying Model for Representing Time-Varying Graphs

1 Introduction

• Existing TVG models extend graphs with time but may lack generality and rely on assumptions not explicitly encoded in their structures.Snapshot models, for example, implicitly assume continuity of node identity across successive snapshots.Source: §1 · p. 3
• The paper proposes a finite discrete TVG model designed to represent diverse dynamic networks without additional assumptions outside the model.The proposal preserves the discrete nature of graphs while incorporating temporal relations between nodes.Source: §1 · p. 3
• The model represents several prior dynamic-network model classes, although those prior models generally cannot represent one another.This comparative representational scope is presented as evidence of the proposed model’s expressive power.Source: §1 · pp. 3–4
• The model intrinsically represents cyclic or periodic behavior in dynamic networks.This capability distinguishes the proposal from previous TVG models described in the introduction.Source: §1 · pp. 3–4
• The paper analyzes the model’s data structures and studies their memory complexity, while organizing the paper around the model, data structures, prior-model representations, and conclusions.The stated practical complexity result is developed in later sections rather than established in the introduction passages supplied here.Source: §1 · pp. 3–4

2 Proposed model for representing TVGs

• A TVG is represented as a two-aspect MAG H = (V,E,T), with edges E ⊆ V × T × V × T connecting node-time pairs.The aspects are vertices and time instants; V, E, and T denote nodes, edges, and time instants.Source: §2 · p. 4
• Each dynamic edge is a directed quadruple (u,t_a,v,t_b), specifying origin node and time together with destination node and time.An undirected relation requires including both reciprocal directed quadruples.Source: §2 · p. 4
• The model classifies edges as spatial, temporal, mixed, or spatial-temporal self-loop edges according to whether their node and time components coincide.These classes cover same-time distinct-node, same-node different-time, distinct-node distinct-time, and same-node same-time connections.Source: §2 · p. 5
• Temporal components may be ordered so dynamic edges become progressive when time advances and regressive when time moves backward.The general definition does not require an order on the time set, but a linear order enables this classification.Source: §2 · p. 5
• Regressive edges support intrinsic representation of cyclic or periodic behavior in dynamic networks.This capability is identified as a distinctive use of the model’s temporal edge structure.Source: §2 · p. 6
• Temporal nodes are ordered pairs (u,t_a), and the temporal-node representation is isomorphic to a directed static graph for analyzing TVG properties and dynamic processes.The isomorphism also underpins the model’s ability to unify representations of several prior TVG model classes.Source: §2 · p. 6

3 Algebraic representations and structures

• The algebraic section covers adjacency tensors, adjacency matrices, incidence matrices, and memory complexity for representing TVGs.The adjacency and incidence representations, together with their algebraic structures, are included in the memory analysis.Source: §3 · p. 6, §3.4 · p. 10

3.1 TVG adjacency tensor

• A TVG adjacency tensor is fourth-order because each dynamic edge is an ordered quadruple of nodes and time instants.Entries corresponding to present dynamic edges are nonzero, while absent edges receive zero values; nonzero values encode edge weights.Source: §3.1 · pp. 6–7

3.2 TVG adjacency matrix

• The adjacency matrix follows from the TVG’s isomorphism to a directed static graph, allowing temporal-node representations to use standard matrix structures.For two aspects, the companion tuple records the number of nodes and time instants to order temporal nodes in the matrix.Source: §3.2 · pp. 7–8
• The adjacency matrix treats each temporal node as a static-graph node, yielding |V|^2 × |T|^2 entries and typically sparse storage.Its block structure separates spatial edges on the main block diagonal from temporal and mixed edges in off-diagonal blocks.Source: §3.2 · pp. 8–9

3.3 TVG incidence matrix

• The incidence matrix is built from the directed static graph induced by temporal nodes, with rows for temporal nodes and columns for TVG edges.For TVG W, the representation has 12 rows, 16 columns, and 192 entries, including values -1 and 1 for edge endpoints.Source: §3.3 · pp. 9–10

3.4 Memory complexity for storing a TVG

• Connected nodes and used time instants can be recovered from dynamic edges, so storing them separately is redundant.The representation therefore stores dynamic edges together with disconnected nodes and unused time instants.Source: §3.4 · p. 11
• MC(H) = Θ(|E(H)|) when disconnected nodes and unused time instants are fewer than dynamic edges.The complete expression is Θ(|V_N(H)| + |T_N(H)| + |E(H)|), so the edge-count result applies when the first two terms are smaller.Source: §3.4 · pp. 12–13
• In most practical cases, few disconnected nodes and unused time instants make dynamic-edge cardinality determine memory usage.The model also expects TVGs to be sparse relative to the squared number of temporal nodes, enabling compact storage similar to sparse matrices.Source: §3.4 · pp. 10, 13

4 A unifying TVG model

• The model represents prior snapshot, CTI, STE, and TME classes as subsets using appropriate subsets of its dynamic-edge types.The analysis groups prior models by representation style and shows each can be directly represented without losing previously obtained results.Source: §4 · pp. 13–14

4.1 Models based on snapshots

• Snapshot models use only spatial dynamic edges, preserve the original edge count and memory complexity, but leave temporal connectivity implicit between snapshots.Their entries occupy the main block diagonal corresponding to snapshots, while temporal connections are not explicitly constructed.Source: §4.1 · pp. 14–16

4.2 Models based on continuous time intervals (CTI)

• CTI representations may require external interval processing to determine transitivity, making paths and connectivity potentially non-intuitive and computationally expensive.Path existence requires intersecting the time intervals associated with successive edges.Source: §4.2 · pp. 17–18
• CTI models can be represented with progressive mixed dynamic edges, and their interval-based representation requires O(η^2) dynamic edges and memory in the analyzed worst case.A CTI model with η intervals is represented with O(η^2) dynamic edges; the first representation retains the original interval information.Source: §4.2 · pp. 16, 17, 20

4.3 Models based on spatial and temporal edges (STE)

• STE models are formalized with spatial and temporal dynamic edges, whereas TME models are represented using temporal and mixed dynamic edges.Both classes are particular cases of the proposed model, although their edge vocabularies differ.Source: §4.3 · p. 21, §4.4 · p. 21

4.5 Overview on the unifying representation of previous models

• Among the analyzed prior classes, none represents all the others, while the proposed model represents all of them and additionally supports intrinsic cyclic behavior through regressive edges.The representation map explains that missing edge types prevent several prior models from representing one another.Source: §4.5 · pp. 22–23, Table 1 · p. 23

• The model represents several previous dynamic-network model classes that generally cannot represent one another and intrinsically captures cyclic behavior.It can also encode transportation schedules for evaluating connection feasibility and delivery times.Source: §5 · p. 24
• For most practical cases, the model's asymptotic memory complexity is determined by the cardinality of the edge set.Source: §5 · p. 24
• When TVG nodes are independent entities at each time instant, the analyzed TVG is isomorphic to a directed static graph.This isomorphism supports analyzing TVG properties and dynamic-process behavior through the corresponding directed graph.Source: §5 · p. 24
• The model derives communicability and connectivity from explicit TVG structure, avoiding external assumptions required by previous works.These properties follow from the underlying dynamic-edge relation, including its transitivity.Source: §5 · p. 24
• Future work will apply the model to dynamic complex networks and study properties such as time centrality for information diffusion.Source: §5 · p. 24