Klaus Wehmuth

Artur Ziviani

Éric Fleury

A Unifying Model for Representing Time-Varying Graphs

Keywords: dynamic networks, temporal networks, graphs, dynamic graphs, complex networks réseaux dynamiques, réseaux temporels, graphes, graphes dynamique, réseaux complexes

We propose a novel model for representing finite discrete Time-Varying Graphs (TVGs). We show how key concepts, such as degree, path, and connectivity, are handled in our model. We also analyze the data structures built following our proposed model and demonstrate that, for most practical cases, the asymptotic memory complexity of our model is restricted to the cardinality of the set of edges. Moreover, we prove that if the TVG nodes can be considered as independent entities at each time instant, the analyzed TVG is isomorphic to a directed static graph. This is an important theoretical result since this allows the use of the isomorphic directed graph as a tool to analyze both the properties of a TVG and the behavior of dynamic processes over a TVG. We also show that our unifying model can represent several previous (classes of) models for dynamic networks found in the recent literature, which in general are unable to represent each other. In contrast to previous models, our proposal is also able to intrinsically model cyclic (i.e. periodic) behavior in dynamic networks. These representation capabilities attest the expressive power of our proposed unifying model for TVGs.

Introduction

Graph theory has been used for the analysis of several networked systems, being at the core of the new field of Network Science. Much of the utility of the graph abstraction resides in the fact that it can represent relations between a set of objects as well as their connectivity properties, which derive from edge transitivity in a straightforward way without the need of further assumptions that are not explicit in the graph abstraction itself. In this context, there is a lot of studies focusing on investigating the behavior of dynamic processes, such as random walks or information diffusion, over complex networks [START_REF] Pastor | Epidemic spreading in scalefree networks[END_REF][START_REF] Kempe | Maximizing the Spread of Influence through a Social Network[END_REF][START_REF] Barrat | Dynamical Processes on Complex Networks[END_REF][START_REF] Iliofotou | Exploiting Dynamicity in Graph-based Traffic Analysis: Techniques and Applications[END_REF].

More recently, there is an increasing interest in investigating not only the process dynamics on networks, but also the dynamics of networks, i.e. when the network structure (nodes and edges) may vary over time [GDM09, FNR + 12, HS13]. This, however, brings a difficulty since the original graph abstraction was not originally created considering time relations between nodes. As a consequence, the need to extend the basic graph abstraction in order to include time relations between nodes arose, leading to many models for Time-Varying Graphs (TVGs) [BXFJ03, Fer04, Hol05, Kos09, TMML09, HS12, CFQS12, KA12].

As recent models appear extending the basic graph concept to include time relations (Section 4 discusses related work), they are nonetheless not general enough to satisfy the needs of different networked systems and also in many cases rely on assumptions that are not explicitly part of the model. For instance, in models based on snapshots (i.e., a series of static graphs), such as those in [START_REF] Bình | Evolving graphs and least cost journeys in dynamic networks[END_REF][START_REF] Ferreira | Building a reference combinatorial model for MANETs[END_REF], it is implicitly assumed that a node in a given snapshot is connected to 'itself' in the next snapshot, making it possible to extend the transitivity of edges over time. This assumption, however, is not made explicit in the snapshot model. Therefore, when analysed without this implicit assumption, a snapshot model is a sequence of disconnected graphs and therefore no connectivity is possible between different time instants. The need to handle this assumption, which is not explicitly part of the model, brings difficulties since the structure of the model by itself is no longer sufficient to properly represent its behavior, making the understanding, usage, and analysis of such models more complex.

In this paper, we propose a new unifying model for representing finite discrete TVGs. Our proposed model is sufficiently general to capture the needs of distinct dynamic networks [AHFVZ12, SVZ12, HS12, GaVSZ13], whereas not requiring any further assumption that is not explicitly contained in the model itself. Further, our model aims at preserving the strictly discrete nature of the basic graph abstraction, while also allowing to properly represent time relations between nodes. Moreover, we prove that if the TVG nodes can be considered as independent entities at each time instant, the analyzed TVG is isomorphic to a directed static graph. This is an important theoretical result because this allows the use of the isomorphic directed graph as a tool to analyze both the properties of a TVG and the behavior of dynamic processes over a TVG. We also demonstrate that, for most practical cases, the asymptotic memory complexity of our TVG model is determined by the cardinality of the set of edges. Furthermore, we also show the unifying properties of our proposed model for representing TVGs by describing how it represents several previous (classes of) models for dynamic networks found in the recent literature, which in general are unable to represent each other. In contrast to previous models, our proposal is able to intrinsically model cyclic (i.e. periodic) behavior in dynamic networks. These representation features attest the expressive power of our proposed unifying model for TVGs.

This paper proceeds as follows. Section 2 introduces our proposed unifying model for representing TVGs and its main properties. Section 3 discusses data structures to properly represent TVGs using our model. In Section 4, we show how our unifying model can be used to represent previous models for dynamic networks while these models in general are unable to represent each other. Finally, we conclude in Section 5.

Proposed model for representing TVGs and its main properties

Time-varying graphs (TVGs) are graphs in which nodes, or edges may vary in time. In this section, we formally define our proposed model for representing TVGs and present its main properties as well. To that end, we use the same notation adopted by [START_REF] Bang | Digraphs: Theory, Algorithms and Applications[END_REF] for directed graphs.

Proposed model for representing TVGs

Our proposed model represents a TVG as an object H = (V, E, T ), where V is the set of nodes, T is the finite set of time instants for which the TVG is defined, and E ⊆ V × T × V × T is the set of edges. As a matter of notation, we denote V (H) as the set of all nodes in H, E(H) the set of all edges in H, and T (H) the set of all time instants in H. We also define n(H) = |V (H)| the number of nodes in H, m(H) = |E(H)| the number of edges in H, and τ (H) = |T (H)| the number of time instants in which H is defined.

A dynamic edge e in a TVG H is defined as an ordered quadruple e = (u, t a , v, t b ), where u, v ∈ V (H) are the origin and destination nodes (u possibly equal to v) while t a , t b ∈ T (H) are the origin and destination time instants, respectively (t a possibly equal to t b ). Therefore, the dynamic edge e = (u, t a , v, t b ) should be understood as a connection from node u at time t a to node v at time t b . As hinted by its temporal nature, a dynamic edge is a directed edge. If one needs to represent an undirected edge in the TVG, both (u, t a , v, t b ) and its reciprocal (v, t b , u, t a ) should be present in E(H). As a matter of notation, in the remaining of the paper, a TVG will be represented by a upper case letter, usually H or K, a node will be represented by a lower case letter, usually u, v, r or s, a time instant will be represented as t a , where the index a denotes its position in time, and a dynamic edge will be represented as the ordered quadruple (u, t a , v, t b ) (or in a shorter form by the letter e).

We define four canonical projections, each projection mapping a dynamic edge into each one of its components:

π 1 : E(H) → V (H) (u, t a , v, t b ) → u, π 2 : E(H) → T (H) (u, t a , v, t b ) → t a , π 3 : E(H) → V (H) (u, t a , v, t b ) → v, π 4 : E(H) → T (H) (u, t a , v, t b ) → t b .
One may decide to classify an edge e = (u, t a , v, t b ) into four classes depending on its temporal characteristic:

1. Spatial edges connect two nodes at the same time instant, e is in the form of e = (u, t a , v, t a ), where u = v; Inria 2. Temporal edges connect the same node at two distinct time instants, e is in the form of e = (u, t a , u, t b ), where t a = t b ;

3. Mixed edges connect distinct nodes in distinct time instants, e is in the form of e = (u, t a , v, t b ), where u = v and t a = t b ;

4. Spatial-temporal self-loop edges connect the same node at the same time instant, e is in the form of, e = (u, t a , u, t a ).

We define a temporal node as an ordered pair (u, t a ), where u ∈ V (H) is a node and t a ∈ T (H) is a time instant. A temporal node is the representation of a given node at a given time instant. The set of temporal nodes in a TVG H is given by V (H) × T (H), the cartesian product of the set of nodes and the set of time instants. We denote V T (H) = V (H) × T (H) as the set of all temporal nodes on TVG H. As a matter of notation, a temporal node is represented by the ordered pair that defines it, e.g. (u, t a ), or as u ta for a short notation. We use the canonical projections π 1 (u t ) and π 2 (u t ) to extract the node and time instant that compose the temporal node. We also use the notation (u, •) to denote a node u at any time instant, which is indeed equivalent to stating that node u ∈ V .

The definition of a TVG H is as general as possible and does not impose any order on the time set T (H). One may want to stick to the classical time notion and impose a total order on T (H). Within such a context where T (H) has a linear order, both mixed or temporal dynamic edges e = (u, t a , v, t b ) can also be classified as progressive or regressive depending on the order of their temporal components. Dynamic edges that are originated at an earlier time instant and destined to a later time instant are progressive (t a < t b ), whereas dynamic edges originated at a later time instant and destined to an earlier time instant are regressive (t a > t b ). Regressive edges are particularly useful for creating cyclic TVGs, which in turn can be applied to model networks with a cyclic periodic behavior. A simple example of this is a wireless DTN (Delay/Disruption-Tolerant Network) [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF] with n nodes, out of which n -1 nodes are fixed and mutually disconnected, while the remaining node is a mobile one that behaves on a cyclic pattern connecting to a single fixed node at each time instant. A similar scheme can be used to model Wireless Sensor Networks (WSNs) with a mobile sink [START_REF] Chatzigiannakis | Efficient data propagation strategies in wireless sensor networks using a single mobile sink[END_REF][START_REF] Vecchio | DEEP: Density-based proactive data dissemination protocol for wireless sensor networks with uncontrolled sink mobility[END_REF] that regularly visits the sensor nodes to gather the most recent monitored information.

A sub-TVG J of the TVG H is defined in a straightforward way: J = (V, E, T ), V (J) ⊆ V (H), E(J) ⊆ E(H), T (J) ⊆ T (H), such that for all e ∈ E(J), π 1 (e), π 3 (e) ∈ V (J) and π 2 (e), π 4 (e) ∈ T (J).

TVG isomorphism

We define the TVG isomorphism as an extension of the concept of the graph isomorphism. Two TVGs H and K are isomorphic if there is a pair of bijective functions f and g, where

f : V (H) → V (K) and g : T (H) → T (K), such that a dynamic edge (u, t a , v, t b ) ∈ E(H) if and only if the dynamic edge (f (u), g(t a ), f (v), g(t b )) ∈ E(K).
Since the TVG isomorphism is an equivalence relation, the set of all TVGs isomorphic to a given TVG H form an equivalence class in the set of all TVGs. This equivalence relation partitions the set of all TVGs. Further, since the functions f and g are bijections, it follows that if two TVGs H and K are isomorphic, they necessarily have the same number of nodes and the same number of time instants, i.e. The TVG isomorphism is not a time order preserving isomorphism. A time order preserving isomorphism can be obtained by further requiring the sets T (H) and T (K) to have a linear order and the function g to be an order isomorphism, which is an order preserving bijection whose inverse is also order preserving. Hence, for any t a , t b ∈ T (H) we have that t a < t b if and only if g(t a ) < g(t b ). Note that since g is a bijection, it follows that t a = t b if and only if g(t a ) = g(t b ).

Isomorphism between TVGs and directed graphs

In this section, we show that there is an isomorphism between TVGs and directed graphs. We also discuss the circumstances under which this isomorphism holds and the properties it preserves.

Theorem 2.1 For every TVG H with n nodes and τ time instants, where n > 1 and τ > 1, there is a directed graph G with n × τ nodes which is isomorphic to H. This directed graph G is unique up to a graph isomorphism.

Proof 2.1 We show that for any given TVG H with n nodes and τ time instants, there is a unique (up to a graph isomorphism) directed graph G with n × τ nodes for which there is a bijective function

f : V T (H) → V (G), such that any dynamic edge (u, t a , v, t b ) ∈ E(H) if and only if the edge (f ((u, t a )), f ((v, t b ))) ∈ E(G).

• Existence of G:

Given an arbitrary TVG H with n nodes and τ time instants, we construct a directed graph G that satisfies the isomorphism conditions. We start with a graph G with n × τ nodes and no edges (E(G) = ∅). Note that the number of nodes in G equals the number of elements in the set

V T (H) = V (H) × T (H), i.e. |V (G)| = |V T (H)| = n × τ .
We then take an arbitrary bijective function f : V T (H) → V (G). Since by construction the sets V T (H) and V (G) have the same number of elements, such bijection exists. Finally, for every dynamic edge (u, t a , v, t b ) ∈ E(H), we add an edge (f ((u,

t a )), f ((v, t b ))) to E(G). Since f is injective, it follows that if (a, t b ) = (c, t d ), then f ((a, t b )) = f ((c, t d )). Therefore each distinct dynamic edge (u, t a , v, t b ) is mapped to a distinct edge (f ((u, t a )), f ((v, t b ))).
As the only edges in E(G) are the ones mapped from dynamic edges in E(H), it follows that (u, t a , v, t b ) ∈ E(H) if and only if (f ((u, t a )), f ((v, t b ))) ∈ E(G), as required. Note that by this property we have that the number of dynamic edges in H is the same as the number of edges in G, i.e. |E(H)| = |E(G)|. This gives us a directed graph G and a bijective function f that satisfy the isomorphism requirements. Therefore, we have shown that the required graph G exists.

• Uniqueness of G:

Let's assume that in addition to the TVG H, the directed graph G, and the bijective function f described above, we also have another directed graph J with n × τ nodes and a bijective function j : V T (H) → V (J), such that any dynamic edge (u, t a , v, t b ) ∈ E(H) if and only if the dynamic edge (j((u, t a )), j((v, t b ))) ∈ E(J). Since both f and j are bijective functions, it follows that the composite function (j • f -1 ) : V (G) → V (J) is also a bijection. Further, from the definitions of f and j, it follows that the nodes w, z ∈ V (G) are adjacent in G if and only if the nodes (j • f -1 )(w), (j • f -1 )(z) ∈ V (J) are adjacent in J. To observe this, note that if the edge (w, z) ∈ E(G), then the dynamic edge 1 (f -1 (w), f -1 (z)) ∈ E(H) and, as a consequence, the edge (j(f -1 (w)), j(f -1 (z))) ∈ E(J). The converse follows from the same argument applied to an edge in E(J). Therefore, G and J are isomorphic directed graphs, and thus G is unique up to a graph isomorphism.

Given the existence and uniqueness of the directed graph G, the existence of the function f , and since H is an arbitrary TVG with n nodes and τ time instants, we conclude that the theorem holds.

Note that once a bijective function f is determined, all the permutations of f are also bijective functions from V T (H) to V (G). Of course, as shown in the second part of the proof of Theorem 2.1, all the graphs generated by these permutations are isomorphic to each other as well.

An intuitive interpretation of this isomorphism is that the temporal information contained on the dynamic edges and by extent in the set T (H) can be injected into the node set of a directed graph which can be constructed in a way to preserve the edge structure of the TVG, i.e. the relations between nodes and time instants present in the TVG.

Since this isomorphism preserves the edge structure of the TVG, the isomorphic directed graph can be used as a tool to analyze properties of the TVG. However, it should be noted that this isomorphism can not preserve all properties of the TVG (since it is not an identity) and, therefore, care should be taken on its use, to make sure that the properties preserved are sufficient to justify the results obtained. For example, a walk on the TVG corresponds to a walk on the temporal node representation of the TVG (see Section 2.8).

Corollary 2.1 Given a TVG H and a directed graph G isomorphic to H, there is a bijective function from E(H) to E(G), built upon the isomorphism characterizing the bijection f , and which takes each dynamic edge in H to its corresponding edge in G.

Proof 2.2 Let H be a TVG and G a directed graph isomorphic to H. Since H and G are isomorphic, a dynamic edge (u, t a , v, t b ) belongs to E(H) if and only if a corresponding edge (f ((u, t a )), f ((v, t b ))) belongs to E(G), and the function f is a bijection from V T (H) to V (J).

Consider the following function

h : E(H) → E(G) (u, t a , v, t b ) → (f (u, t a ), f (v, t b )).
First, note that h is indeed a function, since it has a properly defined domain E(H), codomain E(G), and association rule (u, t a , v, t b ) → ((u, t a ), (v, t b )). Further, note that this association rule is valid since for each e ∈ E(H) there is an element e s ∈ E(G) such that e s = h(e). This is true because since H and G are isomorphic, it follows that if e = (u,

t a , v, t b ) ∈ E(H) then e s = (f (u, t a ), f (v, t b )) ∈ E(G)
. Furthermore, note that h is defined in terms of the bijection f used to construct the isomorphism between H and G and also that h associates each dynamic edge of H with the edge in G corresponding to it in accordance with the isomorphism between H and G.

We now show that the function h is injective. Let e 1 , e 2 ∈ E(H). Without loss of generality, we can consider that e 1 = (u, t a , v, t b ) and e 2 = (r, t c , s, t d ). We intend to show that if h(e 1 ) = h(e 2 ) then e 1 = e 2 . If h(e 1 ) = h(e 2 ), then

(f (u, t a ), f (v, t b )) = (f (r, t c ), f (s, t d )), so that f (u, t a ) = f (r, t c ) and f (v, t b ) = f (s, t d ). Since f is bijective, it follows that u = r, t a = t c , v = s and t b = t d .
Therefore, e 1 = e 2 and so h is injective.

Further, we show that h is surjective. Let e s ∈ G be any edge in the directed graph G. Without loss of generality, we can assume that e s = (w, z), where w, z ∈ V (G) are nodes of the directed graph G. Since G is isomorphic to H, it follows that there is a dynamic edge e = (u, t a , v, t b ) ∈ E(H), such that w = f ((u, t a )) and z = f ((v, t b )). Then, by the definition of h, it follows that e s = (w, z) = h(e) = (f (u, t a ), f (v, t b )). Therefore, for any given edge e s ∈ E(G), there is a dynamic edge e ∈ E(H) such that e s = h(e), and so h is a surjective function.

Since the function h associates each dynamic edge e ∈ E(H) with its isomorphic corresponding edge e s ∈ G, and h is both injective and surjective, the corollary holds.

Order preserving isomorphism

From the TVG definition used in this work, we have that the set T (H) containing the time instants at which the TVG is defined is not required to be an ordered set. As a consequence, the isomorphism defined in Theorem 2.1 does not necessarily preserves time ordering. If, however, a time order preserving isomorphism is required, it can be obtained by imposing additional requirements to the involved sets and functions as explained next.

First, we need the sets T (H) and V T (H) to be totally ordered sets, such that for all t a , t b ∈ T (H) and all u, v ∈ V (H), t a < t b if and only if (u, t a ) < (v, t b ). Since this can not be done directly, we define an equivalence relation in V T (H), partitioning it into equivalence classes and then create an order on these equivalence classes. To achieve this, we define an equivalence relation ∼, such that (u, t a ) ∼ (v, t b ) if and only if t a = t b . The equivalence relation ∼ partitions the set V T (H) into τ equivalence classes, such that two elements of V T (H) are on the same equivalence class if and only if they have the same temporal component. Let T(H) be the set of equivalence classes generated by ∼ on V T (H) and Γ ta ∈ T(H) the equivalence class of ordered pairs (u, t x ), where t x = t a . By construction, each equivalence class Γ ∈ T(H) has the same number of elements, |Γ| = |V (H)| = n, equal to the number of nodes in the TVG H. The set T(H) can be totally ordered in the way desired.

Second, we define a partition on the set V (G) that has τ equivalence classes and each equivalence class contains |V (H)| elements. This is possible since |V (G)| = |V T (H)|. Let T(G) be the set of equivalence classes in this partition. Note that |T(G)| = |T(H)|. We then define a total order over T(G). This establishes an equivalence relation on V (G), which we denote by ≈.

Finally, we define a bijection f : V T (H) → V (G), which not only satisfies the condition for isomorphism (i.e., (u, t a , v, t b ) ∈ E(H) if and only if (f ((u, t a )), f ((v, t b ))) ∈ E(G)), but also is consistent with the partitions in V T (H) and V (G) as well as preserves the order of these partitions. Formally, the condition of being consistent with the partitions on V T (H) and V (G) can be written as: for all t a , t b ∈ T (H) and all u, v ∈ V (H), (u, t a ) ∼ (v, t b ) if and only if f ((u, t a )) ≈ f ((v, t b )). The order preservation condition can be written as: for all t a , t b ∈ T (H) and all u, v ∈ V (H), (u, t a ) < (v, t b ) if and only if f ((u, t a )) < f ((v, t b )).

It remains to be shown that such an order preserving isomorphism in fact exists. We do this by example, showing that the natural isomorphism defined next in Section 2.3.2 is in fact an order preserving isomorphism.

Natural isomorphism

A special case can be constructed, which characterizes a natural isomorphism (i.e. a natural choice of isomorphism), by making the directed graph G such that its node set V (G) is equal to the set V T (H) and using the identity function I : V T (H) → V (G) as the bijective function to characterize the isomorphism.

Note that, in this case, the edges added to the graph G by the process described in Theorem 2.1 are such that for every dynamic edge (u, t a , v, t b ) ∈ E(H) an edge ((u, t a ), (v, t b )) ∈ E(G) exists in the directed graph G.

Inria

To see that the natural isomorphism is also an order preserving isomorphism, note that in this case V T (H) = V (G) such that both sets can be partitioned in the same way and both partitions can be ordered in the same way. By doing this, the identity function naturally is consistent with the partitions and preserves order as required in Section 2.3.1.

Generalized isomorphism

At this point, an interesting supposition is the existence of an isomorphism between the set of all TVGs with finite nodes and time instants to the set of all directed graphs with finite nodes. This supposition is equivalent to state that there is a bijective function from the set of all TVGs to the set of all directed graphs, such that each TVG is associated to a unique graph that preserves the edge topology of the TVG and also that, in the same manner, each graph is associated to a unique TVG, always up to a graph and TVG isomorphism.

This supposition, however, is false. It is possible to associate each TVG with a unique graph that preserves its edge structure, but it is not possible to associate each graph with a unique TVG. This means that there is a function like the one proposed by the initial supposition, but this function is rather surjective and not injective. Therefore, no generalized isomorphism is possible.

To note why this is indeed the case, note that a given directed graph with p nodes can be associated to TVGs with different dimensions, depending on the prime decomposition of p. Consider for instance a directed graph with p = 21, i.e., a directed graph with 21 nodes. This directed graph could be associated with a TVG with 7 nodes and 3 time instants, but also to a TVG with 3 nodes and 7 time instants. Still, there are the two trivial cases of a TVG with 1 node and 21 time instants or a TVG with 21 nodes and 1 time instant-in this case, the directed graph itself. In particular, if p is a prime number, only these two trivial cases are possible.

TVG representation by temporal nodes

In this section, we show that it is possible to create a representation of any given TVG using temporal nodes. This is equivalent to the natural isomorphism between TVGs and directed networks, presented in Section 2.3.2.

From the definition of temporal nodes, we have that given a TVG H, a temporal node is defined as (u, t a ) ∈ V T (H) = V (H) × T (H). Therefore, if V T (H) is considered as the node set of a directed graph, it follows that an edge on this graph is an element of the set V T (H)×V T (H), which is an ordered pair of temporal nodes. For instance, an edge between the temporal nodes (u, t a ) and (v, t b ) is represented as the ordered pair ((u, t a ), (v, t b )) of temporal nodes.

In this environment, given a TVG H, it is straightforward to create a directed graph G = (V T (H), ET (H)), where V T (H) is the temporal nodes set, and ET (H) is obtained from the set E(H) of dynamic edges of the TVG H, such that for all u, v ∈ V (H) and all t a , t b ∈ T (H), the edge ((u, t a ), (v, t b )) ∈ ET (H) if and only if the dynamic edge (u, t a , v, t b ) ∈ E(H). Another way for obtaining the set ET (H) is by using the bijective function h defined in Corollary 2.1. Note that since in this environment the function f used to define the isomorphism between H and G is the identity function I : V T (H) → V T (H), we have that the function h related to the isomorphism between E(H) and ET (H) (see Corollary 2.1) is written as

h : E(H) → ET (H) (u, t a , v, t b ) → ((u, t a ), (v, t b )),
where ET (H) ⊆ V T (H) × V T (H).

RR n°8466

To see that the graph G = (V T (H), ET (H)) is indeed the graph obtained by the natural isomorphism discussed in Section 2.3.2, note that since V T (H) = V (H) × T (H), we have the identity function I : V T (H) → V T (H), and that by the definition of the temporal node representation, for all u, v ∈ V (H) and all t a , t b ∈ T (H), the edge ((u, t a ), (v, t b )) ∈ ET (H) if and only if the dynamic edge (u, t a , v, t b ) ∈ E(H).

For any given TVG H = (V, E, T ), we can now define the function

g : (V (H), E(H), T (H)) → (V T (H), ET (H)) H → (I(V (H), T (H)), h(E(H))),
such that g(H) is the temporal node representation of the TVG H.

The main idea behind the temporal node representation is that if the nodes of a TVG are considered as distinct objects at each time instants, then the TVG can be seen as a simple directed graph. This, however, should not be misunderstood as a statement that a TVG and a directed graph are one and the same object. It is important to remember that in order to make this representation possible, the assumption that each node is a distinct object at each time instant has to be made. We show that some of the properties of the TVG are in fact preserved in this graph representation, which can make the analysis of the TVG easier. Therefore, this representation comes with a caveat, indicating that proper care should be taken to apply this representation only in the cases in which the properties under study are preserved under the temporal node representation of the TVG.

Figure 1(a) shows an illustrative TVG on its native form and Figure 1(b) shows the same illustrative TVG in the form of the temporal node representation. Note that the temporal node representation has six (2 × 3) temporal nodes and same number of edges as the TVG in its native representation. Further, the edges in the TVG and in the graph only differ in their representation. In the native representation of the illustrative TVG, the dynamic edges are represented as an ordered quadruple, whereas in the temporal node representation the corresponding edge is represented as a pair of temporal nodes. Additionally, Figure 1(b) also shows the temporal nodes grouped in a way consistent with the equivalence relation ∼ defined in Section 2.3.1, which groups elements with the same temporal coordinate in equivalence classes. From Figure 1(b), it can also be seen how the temporal node representation preserves the temporal order of the original TVG.

0 1 (0,t0, 0,t1) (1,t0, 1,t1) (1,t1, 0,t1) (0,t1, 1,t1) (0,t1, 0,t2) (1,t1, 1,t2) (a) Native representation of an illustrative TVG (0,t1) (1,t1) (0,t2) (1,t2) (0,t0) (1,t0) ((0,t0), (0,t1)) ((1,t0), (1,t1)) ((1,t1), (0,t1)) ((0,t1), (1,t1)) ((0,t1), (0,t2)) ((1,t1), (1,t2)) (

Aggregated directed graph

The aggregated graph associated to a TVG is a directed graph created by projecting all dynamic edges onto a single graph. In order to obtain the aggregated graph of a TVG, we first define the projection

π : V × T × V × T → V × V (u, t a , v, t b ) → (u, v),
that takes a dynamic edge to an edge by simply dropping the time coordinates of the dynamic edge.

Using this projection, we can now define the function

Agg : (V, E, T ) → (V, V × V ) H → (I(V (H)), π(E(H)),
where I is the identity function in V (H). It follows from this definition that for a given TVG

H, Agg(H) is a directed graph such that if (u, t a , v, t b ) ∈ E(H), then (u, v) ∈ E(Agg(H)).
In this transformation, spatial and mixed edges are mapped to an edge on the aggregated graph, while temporal edges are contracted into a single node. In this way, temporal edges are ignored, which is consistent with the definition that the aggregated graph is a simple directed graph.

Although the concept of aggregated graph is often found in the TVG literature, it should be noted that for a given TVG H, the nodes of the graph Agg(H) in general do not have the same degree of the nodes on H. It should also be noted that the existence of a path connecting two nodes u and v in Agg(H) does not imply the existence of a path connecting nodes u and v on the TVG H (a path in a TVG is formally defined in Section 2.8.3).

In general, the aggregated graph of a TVG is not isomorphic or in any way equivalent to the temporal node representation of the TVG. To see that this is the case, it suffices to note that for a given TVG H, the temporal node representation of

H has |V (H)| × |T (H)| nodes, while Agg(H) has |V (H)| nodes.

Degree

Since dynamic edges are naturally directed, we adopt the same notation as in directed graphs of the indegree of a node u denoted as deg -(u) and the outdegree of a node u denoted as deg + (u).

In addition, we distinguish between node degree and temporal node degree.

In order to properly define the node degree of a TVG, we use the canonical projections defined in Section 2.1. We then define the node outdegree and indegree as

deg + (u) = |{e ∈ E(H)|π 1 (e) = u}|, deg -(u) = |{e ∈ E(H)|π 3 (e) = u}|,
where deg + (u) is the number of dynamic edges originating at node u and deg -(u) is the number of dynamic edges destined to the node u.

The temporal node degree considers the degree of a node at each time instant. This follows directly from the definition of temporal node:

deg + ((u, t)) = |{e ∈ E(H)|π 1 (e) = u, π 2 (e) = t}|, deg -((u, t)) = |{e ∈ E(H)|π 3 (e) = u, π 4 (e) = t}|.
That is, deg + ((u, t)) is the number of dynamic edges originated at a node u at the time instant t, while deg -((u, t)) is the number of dynamic edges destined to node u at time instant t. It follows from these definitions that for any given TVG H, the outdegree of a node u is given by

deg + (u) = t∈T (H) deg + ((u, t)),
and its indegree is given by deg

-(u) = t∈T (H) deg -((u, t)).
Further, we have that

|E(H)| = u∈V (H) deg + (u) = u∈V (H) t∈T (H) deg + ((u, t)),
and

|E(H)| = u∈V (H) deg -(u) = u∈V (H) t∈T (H) deg -((u, t)).

Adjacency

The concept of adjacency in a TVG can be defined in terms of node and edge adjacencies:

• Node adjacency establishes a relation between nodes, where two nodes are considered adjacent if and only if they share a common dynamic edge, i.e. a dynamic edge is incident to both nodes. Therefore, node adjacency is equivalent to the existence of a dynamic edge between the nodes. In other words, in a given TVG H, two nodes u, v ∈ V (H) are adjacent if and only if there is at least one dynamic edge e ∈ E(H) such that u = π 1 (e) and v = π 3 (e). Note that there is no time constraint in the concept of node adjacency. If a dynamic edge is incident to two nodes, they are adjacent nodes regardless of the time instants at which the dynamic edge is incident to each one of them.

• Temporal node adjacency establishes a relation between temporal nodes, i.e. a relation between nodes at specific time instants. As with nodes, temporal nodes are considered adjacent if and only if they share a common dynamic edge. However, differently from the node adjacency, when a dynamic edge is incident to a pair of temporal nodes, the time instants of the dynamic edges matches the time instants of the temporal nodes, both at the origin and the destination. In a given TVG H, two temporal nodes u t , v t ∈ V T (H) are adjacent if and only if there is a dynamic edge e ∈ E(H) such that u t = (π 1 (e), π 2 (e)) and v t = (π 3 (e), π 4 (e)).

• Edge adjacency defines an edge relation where two dynamic edges are considered adjacent if and only if they are incident to the same node at the same time instant. In a given TVG H, two dynamic edges e a , e b ∈ E(H) are adjacent if and only if there is a temporal node

u t ∈ V T (H), such that u t ∈ {(π 1 (e a ), π 2 (e a )), (π 3 (e a ), π 4 (e a ))} and u t ∈ {(π 1 (e b ), π 2 (e b )), (π 3 (e b ), π 4 (e b ))}.
In order to present the relations between the adjacency in a TVG and the adjacency in its isomorphic directed graph G, we introduce the following theorems.

Theorem 2.2 Given a TVG H and its isomorphic directed graph G, a pair of temporal nodes u t , v t ∈ V T (H) is adjacent in H if and only if their corresponding nodes in G are adjacent.

Inria

Proof 2.3 Let H be a TVG, G its isomorphic directed graph and u t , v t ∈ V T (H) a pair of adjacent temporal nodes in H. Since u t and v t are adjacent, it follows that there is a dynamic edge e ∈ E(H) such that u t = (π 1 (e), π 2 (e)) and v t = (π 3 (e), π 4 (e)). Since H and G are isomorphic, it follows from Theorem 2.1 that e ∈ E(H) if and only if the edge e s = (f

(u t ), f (v t )) ∈ E(G). Therefore, since f (u t ), f (v t ) ∈ V (G)
are the nodes in G corresponding to u t and v t , and the edge e s is incident to both of them, the theorem holds.

Theorem 2.3 Given a TVG H and its isomorphic directed graph G, a pair of nodes u, v ∈ V (H) is adjacent in H if and only if there is at least one pair of adjacent nodes r, s ∈ V (G) in the graph G, such that r corresponds to a temporal node u t for which u = π 1 (u t ) and s corresponds to a temporal node v t for which v = π 1 (v t ).

Proof 2.4 Let H be a TVG, G a directed graph isomorphic to H, and u, v ∈ V (H) a pair of nodes in the TVG H. From Theorem 2.2, we have that a pair of nodes r, s ∈ V (G) is adjacent if and only if there is a pair of adjacent temporal nodes u t , v t ∈ V T (H). From the definition of temporal node adjacency, u t and v t are adjacent if and only if there is a dynamic edge e such that u t = (π 1 (e), π 2 (e)) and v t = (π 3 (e), π 4 (e)). Further, from the definition of node adjacency, u and v are adjacent if and only if there is a dynamic edge e such that u = π 1 (e) and v = π 3 (e). Note that π 1 (v t ) = π 3 (e).

Therefore, since by hypothesis u = π 1 (u t ) and v = π 1 (v t ), the theorem holds.

Theorem 2.4 For a given a TVG H and its isomorphic directed graph G, a pair of dynamic edges in H is adjacent if and only if their corresponding edges are adjacent in G.

Proof 2.5 Let H be a TVG and G its isomorphic directed graph as per Theorem 2.1.

• =⇒ Let e 1 , e 2 ∈ E(H) be two adjacent dynamic edges in H. Since they are adjacent, by our definition both edges are incident to the same node at the same time instant. Therefore, without loss of generality, we can assume that e 1 = (u, t a , v, t b ) and e 2 = (v, t b , w, t c ), making both edges incident to node v at time t b . By Theorem 2.1, it follows that there are two edges e 1s , e 2s ∈ G, such that e 1s = (f ((u, t a )), f ((v, t b ))) and e 2s = (f ((v, t b )), f ((w, t c ))). Since both edges e 1s and e 2s are incident to the node f ((v, t b )), they are adjacent edges in G.

• ⇐= Let e 3 , e 4 ∈ E(G) be two adjacent edges in G. Since they are adjacent, they are incident to the same node and thus, without loss of generality, they can be written as e 3 = (a, b) and e 4 = (b, c), where a, b, c ∈ V (G) are nodes in G. Hence, by Theorem 2.1,

f -1 (a), f -1 (b), f -1 (c) ∈ V T (H) are temporal nodes in H and e 3t = (f -1 (a), f -1 (b)) and e 4t = (f -1 (b), f -1 (c)
) are dynamic edges in H. Since both edges are incident to the temporal node f -1 (b), it follows that they are incident to the same node at the same time instant, being therefore adjacent dynamic edges in H.

Since the temporal node representation is a particular case of the isomorphism shown in Theorem 2.1, it follows that Theorems 2.2, 2.3, and 2.4 are also valid for the temporal node representation. This property makes it possible to analyze concepts derived from edge adjacency in the temporal node representation of the TVG.

It is well known that if a pair of nodes u and v are adjacent in a TVG, then these nodes are also adjacent in the aggregated graph of the TVG. However, the reciprocal is not true.

For the dynamic edge adjacency, we have the following theorem. Note that the dynamic edges e 1 and e 2 are not necessarily adjacent in the TVG. For the Theorem 2.5 to hold, it is sufficient that these dynamic edges share the same node, regardless of the time instants. This happens because all information concerning time instants in the dynamic edges is dropped by the projection π. Further, note that the edges e 1 and e 2 do not have to necessarily be both spatial or both mixed.

Walks, trails, paths, and cycles

In this section, we analyze concepts that are derived from the basic concept of adjacency (see Section 2.7). Since in the environment of a TVG the time relations are considered in the same way as relations between nodes, it is natural to use an adjacency definition which takes time relations into account. Therefore, the concepts of temporal node adjacency and edge adjacency are used because they depend not only on the nodes, but also on time instants to determine if adjacency occurs. We show in this section that walks, trails, paths, and cycles, as they are defined for TVGs, are preserved under the isomorphism between TVGs and directed graphs (see Section 2.2), and in particular by the temporal node representation (i.e. natural isomorphism between a TVG and a directed graph), so that properties related to walks, trails, paths, and cycles can be analyzed on the temporal node representation of the TVG.

Walk

We define a walk on a TVG H as an alternating sequence W = [u t1 , e 1 , u t2 , e 2 , u t3 , ..., u t k-1 , e k-1 , u t k ] of temporal nodes u ti ∈ V T (H) and dynamic edges e j ∈ E(H), such that u ti = (π 1 (e i ), π 2 (e i )) and u ti+1 = (π 3 (e i ), π 4 (e i )) for 1 ≤ i < k. Note that from this definition we have that all pairs of consecutive temporal nodes u ti and u ti+1 are adjacent and also that all pairs of consecutive dynamic edges e j and e j+1 are adjacent.

A walk is closed if u t1 = u t k and open otherwise. The set of temporal nodes in the walk W is denoted as V T (W ) and the set of dynamic edges in the walk W is denoted as E(W ). Since the dynamic edges in W contain time instants, we can denote the set of all time instants in W as

T (W ). Further, if W is a walk on a TVG H, then V T (W ) ⊆ V T (H), E(W ) ⊆ E(H) and T (W ) ⊆ T (H).
Note that each dynamic edge e i in a walk W can be determined by the temporal nodes u ti and u ti+1 by writing e i = (π 1 (u ti ), π 2 (u ti ), π 1 (u ti+1 ), π 2 (u ti+1 )). Therefore, W can be fully described by the sequence of its temporal nodes, W V = [u t1 , u t2 , ..., u t k ]. We may refer to a walk using this notation in cases where the precise determination of the edges is not needed. The sequence of temporal nodes W V is not necessarily equal to the set V T (W ) of temporal nodes in the walk, since in W V there may be repeated temporal nodes.

Inria

Further, each dynamic edge e j in a walk W also fully determines the temporal nodes u tj and u tj+1 , since u tj = (π 1 (e j ), π 2 (e j )) and u tj+1 = (π 4 (e j ), π 4 (e j )). Hence, W can also be determined by its sequence of dynamic edges W E = [e 1 , e 2 , ..., e n ]. We may use this notation when the precise identification of the nodes is not needed. The sequence (or list) of edges W E is not necessarily equal to the set of edges E(W ), since there may be repeated edges in W E . The length of a walk is determined by the number of dynamic edges the walk contains, i.e. Len(W ) = |W E |.

As a short notation, in cases where there is no ambiguity, or the identity of the temporal nodes and dynamic edges in the walk is not relevant, we may also identify a walk W only by its start and end nodes as

W = u 1 → u k . Theorem 2.
h : E(H) → ET (H) = E(g(H)) such that h((u, t a , v, t b )) = ((u, t a ), (v, t b )). • =⇒ Let W = [u t1 , e 1 , u t2 , e 2 , u t3 , ..., u t k-1 , e k-1 , u t k ]
be a walk on TVG H and g(H) be the temporal node representation of the TVG H. Since the nodes present in W are temporal nodes, they correspond directly to temporal nodes in g(H), because the bijection between V T (H) and V (g(H)) is the identity. Thus, it is only necessary to translate the dynamic edges e i into edges in E(g(H)). Each dynamic edge e i is determined by the temporal nodes u ti and u ti+1 such that

e i = (π 1 (u ti ), π 2 (u ti ), π 1 (u ti+1 ), π 2 (u ti+1 )). Applying the function h to e i we have that h((π 1 (u ti ), π 2 (u ti ), π 1 (u ti+1 ), π 2 (u ti+1 ))) = ((π 1 (u ti ), π 2 (u ti )), (π 1 (u ti+1 ), π 2 (u ti+1 ))) = (u ti , u ti+1 ) = e si .
Therefore, we have that the sequence G W = [u t1 , e s1 , u t2 , e s2 , u t3 , ..., u t k-1 , e s k-1 , u t k ] is the walk corresponding to W in g(H), since it is the walk composed of the nodes in V (g(H)) corresponding to the temporal nodes in W .

• ⇐= Let G W = [u t1 , e s1 , u t2 , e s2 , u t3 , ..., u t k-1 , e s k-1 , u t k ] be a walk on g(H). Then u ti ∈ V (g(H)) are nodes in g(H) and e si ∈ E(g(H)) are edges in g(H). By construction of g(H), V (g(H)) = V T (H), such that u ti ∈ V T (H) are also temporal nodes in H.

Since W is a walk on the graph g(H), it follows that e si = (u ti , u ti+1 ). Applying h -1 to e si , we have h -1 ((u ti , u ti+1 )) = (π 1 (u ti ), π 2 (u ti ), π 1 (u ti+1 )) = e i , such that the sequence W = [u t1 , e 1 , u t2 , e 2 , u t3 , ..., u t k-1 , e k-1 , u t k ] is the corresponding walk on the TVG H.

Corollary 2.2

The length of a walk W on a TVG H is the same as the length of the corresponding walk G W on the directed graph g(H).

Proof 2.8 It follows from Theorem 2.6 that the sequence of temporal nodes u ti in the walk H is the same as the sequence of temporal nodes u ti in the walk G W . Since each pair of consecutive temporal nodes u ti and u ti+1 determines a dynamic edge in W and also an edge in G W , it follows that the number of dynamic edges in W is the same as the number of edges in G W . Therefore, from the definition of length of a walk, we have that Len(W ) = Len(G W ) and the corollary holds.

Theorem 2.7 Given a TVG H and its aggregated graph Agg(H), the projection of a walk on H onto Agg(H) is a walk on Agg(H).

Proof 2.9 Let H be a TVG, Agg(H) its aggregated directed graph and W = [u t1 , e 1 , u t2 , e 2 , u t3 , ..., u t k-1 , e k-1 , u t k ] a walk on TVG H. If the walk W only has spatial or mixed dynamic edges, then this theorem holds as a direct consequence of Theorem 2.5, since consecutive edges in a walk are adjacent in the TVG and therefore are incident to the same node. If, however, the walk has temporal dynamic edges, they contract to a single node and, therefore, are not reflected in Agg(H). When this happens, note that the nodes before and after each temporal edge are the same. This happens because a temporal edge has the form e = (u, t a , u, t b ), connecting a node to itself at different time instants. Therefore, every sequence of temporal dynamic edges can be ignored and the theorem holds.

Trail

We define a trail in a TVG H as a walk on H where all edges are distinct. We can identify a trail Proof 2.10

W = [u t1 , e 1 , u t2 , e 2 , u t3 , ..., u t k-1 , e k-1 , u t k ] with the TVG H W = (V(W), E(W), T(W)). Since V (W ) ⊆ V (H), E(W ) ⊆ E(H)
• =⇒ Let H W be a trail on H and let g(H) be the temporal node representation of the TVG H. Since H W is a trail, it is also a walk. Hence, by Theorem 2.6, there is a corresponding walk G W on g(H). Since H W is a trail on H, we have that all dynamic edges e s ∈ E(H W ) ⊆ E(H) are distinct. From Corollary 2.1, we have that there is a bijection h : E(H) → E(g(H)) and, therefore, since the dynamic edges e s in H W are distinct, so are the corresponding edges in G W . Since G W is a walk on g(H) and its edges are distinct, it follows that G W is a trail on g(H).

• ⇐=

Let G W be a trail on g(H), which is the temporal node representation of a TVG H. Since G W is also a walk on g(H), by Theorem 2.6, there is a corresponding walk H W on H. Since G W is a trail, the edges e si ∈ E(G W ) ⊆ E(g(H)) are all distinct. As that by Corollary 2.1 there is a bijection h : E(H) → E(g(H)), it follows that the corresponding dynamic edges in the walk H W are also distinct. Therefore, since H W is a walk and has distinct edges, it follows that H W is a trail on the TVG H.

A trail is closed when the first and last temporal nodes are the same, i.e. u t1 = u t k , and open otherwise. A closed trail is also called a tour or a circuit.

From Theorem 2.7, we have that the projection of a trail W onto the aggregated graph of H is a walk. To see that this projection is not necessarily a trail, consider the trail W = [(u, t 1 ), (u, t 1 , v, t 2 ), (v, t 2 ), (v, t 2 , w, t 3 ), (w, t 3 ), (w, t 3 , u, t 4 ), (u, t 4 ), (u, t 4 , v, t 5 ), (v, t 5 )]. The projection of W onto Agg(H) is the walk W agg = [u, (u, v), v, (v, w), w, (w, u), u, (u, v), v]. Note that the edge (u, v) appears twice in W agg . Therefore, the walk W agg is not a trail.

Since a trail is also a walk, the length of a trail is determined in the same way as the length of a walk, by the number of edges. In particular, it follows from Corollary 2.2 that the length of a trail H W on a TVG H is the same as the length of the corresponding trail G W on g(H), i.e. Len(H W ) = Len(G W ).

Path

We define a path on a TVG H as a walk on H where all temporal nodes are distinct. We can identify a path P = [u t1 , e 1 , u t2 , e 2 , u t3 , ..., u t k-1 , e k-1 , u t k ] with the TVG H P = (V(P), E(P), Inria T(P)), where V (P ), E(P ), and T (P ) are the sets of temporal nodes, dynamic edges, and time instants on the path, respectively. Since V (P ) ⊆ V (H), E(P ) ⊆ E(H), and T (P ) ⊆ T (H), it follows that the path P is a sub-TVG of H. Theorem 2.9 A walk P on H is a path on H if and only if there is a corresponding path G P on g(H).

Proof 2.11 Since P is also a walk on H, we have from Theorem 2.6 that P is a walk on H if and only if G P is a walk on g(H). Therefore, the only point left to be shown is that all nodes in P are distinct if and only if all nodes in G P are distinct. However, it also follows from Theorem 2.6 that the temporal nodes in P and in G P are the same. Therefore, if the nodes of P are distinct, so are the nodes of G P , and the theorem holds.

From Theorem 2.7, we have that the projection of a path P onto the aggregated graph of H is a walk. To show this, we use the same example presented for trails. Let the sequence P = [(u, t 1 ), (u, t 1 , v, t 2 ), (v, t 2 ), (v, t 2 , w, t 3 ), (w, t 3 ), (w, t 3 , u, t 4 ), (u, t 4 ), (u, t 4 , v, t 5 ), (v, t 5 )] be a path on TVG H. The projection of P onto Agg(H) is the walk W agg = [u, (u, v), v, (v, w), w, (w, u), u, (u, v), v]. Note that the node u appears twice in W agg . The walk W agg is thus not a path.

Since a path is also a walk, the length of the path is also determined by the number of edges on it. Further, it follows from Corollary 2.2 that the length of a path P on a TVG H is the same as the length of the corresponding path G P on g(H), i.e. Len(P ) = Len(G P ).

This notion of path stems from the adjacency definitions used on TVGs, where both nodes and time instants are considered to define adjacency (i.e. two dynamic edges are adjacent if and only if they are both incident to a node at the same given time instant). Therefore, this definition is consistent with the walk and trail definitions stated before, since all of them are based on this same adjacency notion.

However, the path definition we present is not the same that is usually used, in which a path can not pass twice through a same node, regardless of time instants. We present this definition since, as stated above, it is consistent with the development started on the walk definition and also because it leads to interesting and useful results, such as that a path is preserved by the natural isomorphism (i.e. temporal nodes representation). Further, if required, the more traditional path definition can be easily reached, since it coincides with the projection of the path onto the aggregated graph of the TVG. Note that this is consistent with the idea that the aggregated graph and projections over it are obtained by ignoring the time instant coordinates present on dynamic edges.

Once we have the path definition, it can be seen that a mixed edge can be decomposed into a pair of temporal and spatial edges forming a path with two dynamic edges. However, it should be noted that such a decomposition leads to a TVG that is topologically different (and therefore not isomorphic) as compared with the original TVG with the mixed edge. To see that this is indeed the case, note that when this decomposition is performed, it is necessary to create a temporal and a spatial dynamic edge (unless they already exist) and that the original mixed edge is then removed. Since in any case the original TVG and the TVG with the decomposition don't have the same number of edges, they cannot be isomorphic. Similarly, any path containing mixed dynamic edges can be decomposed into a path containing only temporal and spatial dynamic edges.

Cycle

A cycle on a TVG is defined as a closed path, i.e. a path that starts and ends on the same temporal node. Theorem 2.10 A path P on a TVG H is a cycle if and only if the corresponding path G P in g(H) is a cycle. Proof 2.12 From Theorem 2.9, we have that P is a path on H if and only if G P is a path on g(H). Hence, we only need to show that P starts and ends on the same temporal node if and only if G P does the same. It follows from Theorem 2.6 that the sequence of temporal nodes in P and in G P is the same. Therefore, if P starts and ands on a given temporal node u t , so does G P and the theorem holds.

Additionally, since a cycle is a special case of a path, it follows that the length of a cycle is determined in the same way as the length of a path. Further, the length of a cycle P on H is the same as the length of the corresponding cycle G P on g(H).

We define the girth of a TVG H as the length of the shortest cycle in H. If H has no cycle, we consider that its girth is infinite. It follows directly from Theorem 2.10 and Corollary 2.2 that a TVG H and its temporal node representation g(H) have the same girth.

If a cycle on a TVG is constructed using only spatial dynamic edges, this cycle is equivalent to the concept of cycles on a directed graph. Nevertheless, if a cycle contains any dynamic edge which has a non-zero temporal component (i.e. a temporal or mixed edge), then the cycle has to contain a regressive dynamic edge, since the presence of progressive edges makes the use of a regressive edge necessary to make it possible for a path to return to the temporal node where it started.

Shortest paths on a TVG

Given two temporal nodes u ta , u t b ∈ V T (H) in a TVG H, we define the shortest path between u ta and u t b as the path with the smallest length starting at temporal node u ta and ending at temporal node u t b .

We can define four distinct variants of shortest path on a TVG:

1. Shortest path from a temporal node to a temporal node, i.e. (u, t a ) → (v, t b );

2. Shortest path from a node to a temporal node. This is the shortest path starting at any temporal node u t such that π 1 (u t ) = u and ending at the temporal node (v, t b ); i.e. (u, •) → (v, t b ) ;

3. Shortest path from a temporal node to a node. This is the shortest path starting at a temporal node (u, t a ) and ending at any temporal node v t such that π 1 (v t ) = v; i.e. (u, t) → (v, •);

4. Absolute shortest path. This is the shortest path from a node to another node. In other words, this is the shortest path starting at any temporal node u t such that π 1 (u t ) = u and ending at any temporal node v t such that π 1

(v t ) = v; i.e. (u, •) → (v, •).
Note that even though the variants 2, 3, and 4 involve the concept of nodes, a path always starts and ends on a temporal node. The meaning of the nodes in the shortest path variants is the freedom to select a temporal node at any time instant, such that the path is minimized.

Theorem 2.11 A path P between two temporal nodes u ta and u t b on a TVG H is a shortest path between these nodes if and only if the corresponding path G P in g(H) is a shortest path between u ta and u t b on g(H).

Inria

Proof 2.13

• =⇒ (by contradiction) Let u ta , u t b ∈ V T (H) be two temporal nodes on a TVG H and P be a shortest path from u ta to u t b . Further, let G P be the corresponding path from u ta to u t b on the graph g(H). From Corollary 2.2, we have that Len(P ) = Len(G P ). Let's suppose that G P is not a shortest path from u ta to u t b on g(H). This means that there is a path G P S from u ta to u t b on g(H), such that Len(G P S ) < Len(G P ). Then, by Theorem 2.9 and Corollary 2.2, there must be a corresponding path P S from u ta to u t b on H, such that Len(P S ) < Len(P ). This is a contradiction, since P is a shortest path from u ta to u t b on H. Therefore, G P is a shortest path from u ta to u t b on g(H).

• ⇐= (by contradiction)

Let u ta , u t b ∈ V (g(H) be two temporal nodes on g(H) and G P be a shortest path from u ta to u t b . Further, let P be the corresponding path from u ta to u t b on the TVG H. From Corollary 2.2, we have that Len(G P ) = Len(P ).

Let's suppose that P is not a shortest path from u ta to u t b on TVG H. Then, there must be a path P S from u ta to u t b in H, such that Len(P S ) < Len(P ). Thus, from Theorem 2.9 and Corollary 2.2, there must be a corresponding path G P S from u ta to u t b on g(H), such that Len(G P S ) < Len(G P ). This is a contradiction, since G P is a shortest path from u ta to u t b on g(H). Therefore, P is a shortest path from u ta to u t b on the TVG H.

Figure 2 shows a simple example of a TVG for illustrating TVG shortest paths. The shortest path from (0, t 0 ) to (1, t 2 ) is the sequence [(0, t 0 ), (0, t 1 ), (1, t 1 ), (1, t 2 )] and has length 3, while the shortest path from (0, t 0 ) to (1, •) is formed by [(0, t 0 ), (0, t 1 ), (1, t 1 )] and has length 2. In the same way, the shortest path from (0,

•) to (1, •) is [(0, t 1 ), (1, t 1 )], while the shortest path from (0, •) to (1, t 2 ) is [(0, t 1 ), (1, t 1 ), (1, t 2 )].

Strongly connected TVG

We define a strongly connected TVG as a TVG H in which for all pairs of nodes u, v ∈ V (H) there is a path u → v and also a path v → u. Nevertheless, this does not mean that any pair of nodes is capable of communicating at all times. It only means that each node is capable of eventually accessing any other node at some time instant. Note that in the temporal node representation a strongly connected TVG is not necessarily a strongly connected graph. For the graph to be strongly connected, every pair of temporal nodes would have to communicate, which is not required for the TVG to be strongly connected. Figure 3 shows an example of a strongly connected TVG. The TVG shown in Figure 3 is strongly connected because there is a path from node 0 to node 1, a path from node 0 to node 2, a path from node 1 to node 0, a path from node 1 to node 2, a path from node 2 to node 1, and a path from node 2 to node 0. However, the temporal node representation of the TVG is clearly not strongly connected. Additionally, in the TVG case, strong connectivity has to be considered over time. If no time restriction is stated, we consider that the connectivity is defined over all time instants present on the TVG. However, connectivity can also be defined over a subset of the time instants of the TVG. When this happens, the connectivity becomes stronger as the time interval over which it is defined becomes smaller. For instance, the TVG shown in Figure 3 is strongly connected if all time instants are considered. However, the sub-TVG obtained when only instants t 0 and t 1 are considered is not strongly connected, since in this sub-TVG node 2 is an isolated node, i.e. it has no dynamic edges incident to it.

Closed strongly connected TVG

We define a closed strongly connected TVG as a TVG H on which for all pairs of nodes in H there is a path from each node to itself that passes through the other node of the pair. This means that for all pair of nodes u, v ∈ V (H) there is a path P u = u → u, such that there is a temporal node v t ∈ V (P u ) for which v = π 1 (v t ), and also a path P v = v → v such that there is a temporal node u t ∈ V (P v ) for which u = π 1 (u t ). Note that a path P = u → u is not necessarily a cycle, since the temporal nodes (u, t a ) where the path start and (u, t b ) where it ends may have time instants t a = t b . Figure 4 shows an example of a closed strongly connected TVG. There is a path P 0 = 0 → 0 which passed through node 1 and also a path P 1 = 1 → 1 which passes through node 0. Note that neither P 0 = [(0, t 0 ), (1, t 1 ), (0, t 2 )] nor P 1 = [(1, t 1 ), (0, t 2 ), (1, t 3 )] are cycles.

In this kind of connectivity, we also have that the temporal node representation of a closed strongly connected TVG is not necessarily a strongly connected directed graph. This can easily be seen in Figure 4. This sort of connectivity also depends on the considered set of time instants. For instance, in Figure 4, the sub-TVG having only time instants t 0 , t 1 , and t 2 is not closed strongly connected because since t 3 is not present, there is no path from node 1 to node 1 passing through node 0. The closed strong connectivity can also be made stronger by imposing tighter time constraints to it. For instance, the TVG shown in Figure 5 is closed strongly connected, however, in this case the sub-TVGs containing only time instants t 0 , t 1 , t 2 and t 1 , t 2 , t 3 are also closed strongly connected.

Temporal node strongly connected TVG

This is the strongest form of connectivity. This kind of connectivity happens when the temporal node representation of the TVG is also strongly connected. This means that for a given TVG H to be temporal node strongly connected, for every pair of temporal nodes u t , v t ∈ V T (H) there is a path P ut = u t → v t and a path P vt = v t → u t . This form of connectivity on a given TVG H happens if and only if its temporal node representation g(H) is also a strongly connected directed graph. Further, unless the TVG is trivial, having only one time instant, this form of strong connectivity implies the existence of temporal cycles.

Representations and algebraic structures of a TVG

In this section, we discuss ways to properly represent a TVG using our proposed model. Similarly to static graphs, a TVG can be fully represented by an algebraic structure. We thus present forms of TVG representation based on adjacency and incidence. The algebraic representations are in the form of tensors and matrices. The tensor form is regarded as the canonical form of representing the TVG, while the matrix form is based on the natural isomorphism (i.e. temporal node representation) stated in Sections 2.2 and 2.4. The TVG adjacency tensor and its matrix form are discussed in Sections 3.1 and 3.2, respectively. Likewise, the TVG incidence tensor and its matrix form are discussed in Sections 3.3 and 3.4, respectively. In order to illustrate such representations, we use the TVG W presented in Figure 6, where spatial edges are represented by solid arrows and temporal edges by dashed arrows. Finally, in Section 3.5, we analyze the memory complexity for storing a TVG using our model.

TVG adjacency tensor

The adjacency tensor follows from the adjacency matrix widely used to represent static graphs. However, since the dynamic edges used in the TVG are ordered quadruples, this representation has to be done by means of a 4th order tensor.

We then define the adjacency tensor of a TVG H as a 4th order tensor A(H) with dimension

|V (H)| × |T (H)| × |V (H)| × |T (H)| that
has an entry for every possible dynamic edge in H. Each dynamic edge present in the TVG H is represented by a non-zero entry in the adjacency tensor A(H), while all other entries have a zero value. The non-zero entries represent the weight of the corresponding dynamic edge in the represented TVG. In the case of a unweighted TVG, the non-zero entries corresponding to the dynamic edges present in the TVG have value 1. The notation A(H) u,ta v,t b is used to identify the entry corresponding to the dynamic edge (u, t a , v, t b ) of the TVG H.

As an example, the adjacency tensor of the TVG W depicted in Figure 6 has dimension 4 × 3 × 4 × 3, having a total of 144 entries. For instance, the pair of dynamic spatial edges connecting node 0 at time t 0 to node 3 at time t 0 is represented by the entries A(W ) 0,t0 3,t0 and A(W ) 3,t0 0,t0 , where both carry value 1 as the TVG W is unweighted. Note that, even though the adjacency tensor A(H) has dimension |V (H t )|×|T (H t )|×|V (H t )|× |T (H t )|, only the entries corresponding to dynamic edges present in the TVG H have non-zero values.

Matrix form of the TVG adjacency tensor

Since Theorem 2.1 ensures that a TVG has a directed static graph that is isomorphic to it, it follows that the TVG can be represented by an adjacency matrix. Therefore, we choose the adjacency matrix of the directed static graph obtained from the temporal node representation to be the matrix form of the TVG adjacency tensor.

To get the matrix representation of the TVG adjacency tensor using the temporal node representation (i.e. natural isomorphism) presented in Section 2.4, we only need to consider that each temporal node (u, t a ) can be thought of as a node in a static graph. This static graph has |V | × |T | nodes and, as a consequence, its adjacency matrix has

|V | × |T | × |V | × |T | = |V | 2 × |T | 2
entries. Since the non-zero entries of this matrix correspond to the dynamic edges of the TVG, further analysis show that this matrix is usually sparse and can therefore be stored in an efficient way.

Figure 7 shows the matrix representation obtained for the illustrative TVG W shown in 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Figure 6. From Figure 7, we highlight that the matrix form of the TVG adjacency tensor has interesting structural properties. First, each one of the four nodes (identified as 0, 1, 2, and of the TVG W clearly appears as a separate entity in each of the three time instants (t 0 , t 1 , and t 2 ) that compose the TVG W . Second, the main block diagonal (lightly shaded) contains the entries corresponding to the spatial edges at each time instant. In these three blocks the entries corresponding to the spatial edges of the TVG carry value 1. Third, the unshaded entries at the off-diagonal blocks correspond to the temporal edges. The eight progressive temporal edges present at the TVG W are indicated by the value 1 on the first superior diagonal. Finally, the dark shaded entries are the ones that correspond to the mixed edges. Since no mixed edges are present in the example TVG W , all these entries contain value 0. Further, we remark that the entries corresponding to progressive (mixed and temporal) edges are above the main block diagonal, whereas the edges corresponding to regressive edges appear below the main block diagonal. All these structural properties derive from the order adopted for representing the nodes and time instants present in the TVG and can be readily verified in the matrix form in a convenient way.

Inria 0 1 2 3 0 1 2 3 0 1 2 3 t0 t1 t2 t0 t1 t2 0 1 2 3 0 1 2 3 0 1 2 3 Mat(A G1 ) = 2
Note that the procedure used to obtain the matrix form of the adjacency tensor is the wellknown matricization or unfolding of a tensor [START_REF] Kolda | Multilinear operators for higher-order decompositions[END_REF]. In fact, the matricization of the adjacency tensor can be seen as an equivalent form of Theorem 2.1, since it shows that a 4th order tensor of dimension |V | × |T | × |V | × |T | can be written as a square matrix with the same number of entries. Further, since each entry of the matrix corresponds to an entry in the tensor, the process can be reversed, obtaining the corresponding tensor from its matrix form. Hence, in agreement with the stated in Section 2.2, while the process of obtaining the matrix form from the higher order tensor is straightforward, the process of obtaining the tensor from the matrix form can only be done if the dimensions of the tensor form are known.

TVG incidence tensor

The representation used on the incidence tensor relates the dynamic edges present in the TVG with the nodes and time instants defined in the TVG, leading to a 3rd order tensor.

We define the incidence tensor of a TVG H as a 3rd order tensor C(H) with dimension

|E(H)| × |V (H)| × |T (H)|.
Each entry of this incidence tensor corresponds to a dynamic edge, node, and time instant combination. An entry has value -1 if the dynamic edge corresponding to this entry is originated at the node and time instant represented by the entry. Conversely, an entry has value 1 if the dynamic edge corresponding to the entry has as destination the node and time instant represented by the entry. An entry has value 0 if there is no dynamic edge related to the node and time instant represented by the entry. This representation usually does not carry the weight of the edges, just an indication of their origin and destination. For instance, assuming that the dynamic edge (0, 0, 0, 1) of the TVG W depicted in Figure 7 is labeled as e 0 , then the entry C(H) t0 0,e0 has value -1, the entry C(H) t1 0,e0 has value 1, and all other entries C(H) t n,e0 , except the previous two, have value 0. Further, the incidence tensor representing the TVG W shown in Figure 7

Matrix form of the TVG incidence tensor

The matrix form of the incidence tensor of a TVG is the incidence matrix corresponding to the directed static graph obtained though the temporal node representation presented in Section 2.2. For instance, considering the TVG W shown in Figure 6, there is a temporal edge connecting node 0 at time t 0 to node 0 at time t 1 . Without loss of generality, we can label this edge as e 0 and assign it the coordinate 0 for the edge dimension of the incidence tensor. As a consequence, this edge is represented in the incidence tensor by setting C 0 0,0 = -1 and C 1 0,0 = 1. Taking the temporal edge connecting node 0 at time t 1 to node 0 at time t 2 and labeling it as e 1 , its representation on the incidence tensor is C 1 0,1 = -1 and C 2 0,1 = 1. By repeating this procedure for each edge in the TVG, the corresponding incidence tensor is created. Since the TVG W has 16 edges, being 8 temporal edges and 8 spatial edges, 4 nodes, and 3 time instants, the corresponding incidence tensor has a total of 4 × 16 × 3 = 192 entries, from which 160 carry value 0, 16 carry value -1, and 16 value 1. Note that the resulting matrix has 12 rows (for 3 times and 4 nodes) and 16 columns, one for each edge in the TVG, totalizing 12 × 16 = 192 entries.

Figure 8 shows the matrix representation of the incidence tensor corresponding to the TVG W shown in Figure 6. In this representation, the eight temporal edges present in the TVG are labeled as edges e 0 to e 7 and the 8 spatial edges as edges e 8 to e 15 . Considering this labeling, it is straightforward to verify the correspondence of the incidence tensor in matrix form to the TVG.

The matrix form representation of the incidence tensor is compatible with the isomorphism between the TVG and a static graph stated in Theorem 2.1. Indeed, the matrix form of the incidence tensor can also be seen as the incidence matrix of the temporal node representation of the TVG shown in Figure 6. The matrix form of the incidence tensor can also be seen as a matricization of this tensor, where the unfolding is done in a way that the resulting matrix coincides with the incidence matrix of the temporal node representation.

1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 0 1 2 3 0 1 2 3 0 1 2 3
Figure 8: The matrix form of the incidence tensor of TVG W .

Memory complexity for storing a TVG

In this subsection, we analyze the memory complexity for storing a TVG. This analysis is valid for the TVG representations based on adjacency and incidence as well as their corresponding algebraic structures, which have all been discussed in Sections 3.1 to 3.4.

In the general case, TVGs may have disconnected nodes or unused time instants. A disconnected node is defined as a node that has no dynamic edge incident to it, i.e. a node with no connection at any time instant. In a similar way, an unused time instant in a TVG is defined as a time instant at which there is no dynamic edge originated from or destined to it. In most practical cases, however, a TVG is expected to have none or very few disconnected nodes as well as a unused time instants as compared with the total number of nodes or time instants, respectively.

We show that when a TVG has no disconnected nodes and unused time instants, or if the number of disconnected nodes and unused time instants is significantly lower than the number of dynamic edges, then the amount of storage needed to represent a TVG is determined by the number of dynamic edges in the TVG. In other words, we show in this section that in most practical cases the memory complexity M C (H) for storing a given TVG

H is M C (H) = Θ(|E(H)|)
, where E(H) is the set of dynamic edges in the TVG H.

The first step to achieve this is to show that the set of connected nodes and the set of used time instants of a TVG can be recovered from the set of dynamic edges. Lemma 3.1 shows this by using the dynamic edge definition and the canonical projections defined in Section 2.1. Lemma 3.1 In any given TVG H, the set of connected nodes and the set of used time instants can be recovered from the set E(H) that contains the dynamic edges of H. Proof 3.1 Let V C (H) be the set of connected nodes on TVG H. We now show that V C (H) can be constructed from the set E(H). Since V C (H) contains only connected nodes, for every u ∈ V C (H) there is at least one dynamic edge incident to u. Let e u ∈ E(H) be a dynamic edge incident to node u. Then, either e u is of the form (u, •, •, •) or of the form (•, •, u, •), and therefore, either u = π 1 (e u ) or u = π 3 (e u ). Therefore, we can write V C (H) as

V C (H) = e∈E(H) {π 1 (e), π 3 (e)} .
We now use a similar reasoning to recover the set of used time instants from the set E(H). Let T U (H) be the set of used time instants in H and let t u be a used time instant. Then, there is at least one dynamic edge e u ∈ E(H) of the form

(•, t u , •, •) or (•, •, •, t u ) such that t u = π 2 (e u )
or t u = π 4 (e u ). Hence, we can write T U (H) as

T U (H) = e∈E(H) {π 2 (e), π 4 (e)} .
Since Lemma 3.1 shows that the both sets of connected nodes and used time instants in a given TVG H can be recovered from the set of dynamic edges E(H), we can conclude that such information is redundant and does not need to be stored to represent a TVG. Therefore, to represent any given TVG H, it suffices to store the set of dynamic edges E(H) as well as the sets of disconnected nodes and unused time instants of the TVG.

We now demonstrate in Theorem 3.1 that when the sets of disconnected nodes and unused time instants of a TVG are significantly smaller than the set of dynamic edges, which is actually expected in most practical cases, then the asymptotic memory complexity of the TVG representation is determined by the cardinality of the set of dynamic edges. Proof 3.2 Let H be an arbitrary TVG, E(H) its set of dynamic edges, V C (H) its set of connected nodes, V N (H) its set of disconnected nodes, T U (H) its set of used time instants, T N (H) its set of unused time instants, and M C (H) the memory complexity for storing the TVG H. Note that

V (H) = V C (H) ∪ V N (H) and T (H) = T U (H) ∪ T N (H), whereas V C (H) ∩ V N (H) = ∅ and T U (H) ∩ T N (H) = ∅.
Since Lemma 3.1 shows that V C (H) and T U (H) can be recovered from E(H), it follows that to store a representation of H in memory, it suffices to store E(H), V N (H), and T N (H). We now analyze the asymptotic bounds for the memory complexity for storing these sets, together with the assumption that

|V N (H)| + |T N (H)| |E(H)|.
• Lower bound for M C (H): Since for storing the set E(H) it is necessary at least to store an ordered quadruple for each dynamic edge e ∈ E(H), the memory needed is

c 1 × |E(H)|,
where c 1 is an integer constant. To store the set V N (H) it is necessary to store all nodes u ∈ V N (H) and therefore the memory needed is c 2 ×|V N (H)|, while to store the set T N (H) it is necessary to store all time instants u ∈ T N (H), leading to a memory need of c 3 ×|T N (H)|. Therefore, the total memory need is at least

c 1 × |E(H)| + c 2 × |V N (H)| + c 3 × |T N (H)|, and M C (H) = Ω(|E(H)| + |V N (H)| + |T N (H)|). Finally, from our assumption that |V N (H)| + |T N (H)| |E(H)|, we conclude that M C (H) = Ω(|E(H)|).

Inria

• Upper bound for M C (H): On the upper bound analysis, we see that the information to be stored is at most the same three sets E(H), V N (H), and T N (H), which had to be stored in the lower bound analysis. Therefore, we conclude that

M C (H) = O(|E(H)|). Since M C (H) = Ω(|E(H)|) and also M C (H) = O(|E(H)|),

Unifying the representation of previous models

In this section, we show that the TVG model we propose can be used to represent many previous models found in the literature. Further, these models are not always capable of representing each other and none of them has the same representation range of the unifying model we propose.

In order to assert that all the considered models can be directly represented by our model, we show that each of these models is in fact a subset of what is representable in our model and can therefore be easily represented in our model, maintaining any previously obtained result as at least valid on a special case. To achieve this, we show that each of the studied models can be represented in our TVG model by using only a subset of the types of dynamic edges available on our model (see Section 2.1). We achieve this by presenting the general structure of the matrix form of the adjacency tensor of the TVG that represents the model under study. We establish a set of four nodes V = {0, 1, 2, 3} and a set of three time instants T = {t 0 , t 1 , t 2 } to be used to illustrate all of the following analyses. This is done without loss of generality, since the same procedure could be applied to any set of nodes and time instants present in a TVG.

To show the representation in our model of the different previous TVG models found in the literature, we group them into classes that can be represented in our unifying model in similar ways and analyze these classes in the remaining of this section.

Models based on snapshots

Some snapshot models for TVGs adopt an aggregate graph and a sequence of successive state subgraphs that represent the network in a discrete way as time passes. Some examples are the models proposed by Xuan et al. [START_REF] Bình | Evolving graphs and least cost journeys in dynamic networks[END_REF] and Ferreira [START_REF] Ferreira | Building a reference combinatorial model for MANETs[END_REF]. We also consider in this same class of snapshot models the models proposed by Holme [START_REF] Holme | Network reachability of real-world contact sequences[END_REF] and Holme and Saramäki [START_REF] Holme | Temporal networks[END_REF], where edges are represented as triples of the form (i, j, t) meaning the existence of a contact between nodes i and j at time t. Still under this same class, we also consider the models proposed by Tang et al. [TMML09, TSM + 10, TMM + 10], as well as all other models in which the TVG is proposed as a sequence of static graphs (i.e., the snapshots), each of them representing the TVG at a given time instant.

Snapshot models are widely used in the literature and in general give an intuitive and straightforward notion of TVGs. Nevertheless, the snapshot models also demand some assumptions to be made without having them explicitly constructed in the model. For instance, it is usually assumed in such snapshot models that the nodes have a sort of memory that allows the transitivity induced by the edges to propagate on each node over time. This means that a path can be constructed passing through a given node even if this node is disconnected from all others during a period of time, meaning that the node is capable of retaining the edge transitivity during the period of disconnection. Even though this behavior is straightforward and intuitively expected in many cases, it is not constructed within the model and has to be assumed as an additional (external) property of the model, resulting that this assumption has also to be incorporated into the algorithms used with those model and thus making these algorithms dependent of these external assumptions.

From the analysis of the snapshot models, we remark that clearly they only use edges connecting nodes in the same given time instant. This is consistent with the concept of spatial dynamic edges proposed in our model. In this way, all the TVGs constructed in this class of snapshot models can be represented in our model by using only spatial dynamic edges, given that all the necessary nodes and time instants are present in our model. Thus, a TVG with four nodes and three time instants in this class of snapshot model would be represented in our model by a TVG whose adjacency tensor in matrix form is as the one presented in Figure 9. The entries containing "*" may have non-zero values, indicating the potential presence of a spatial edges. Note that all the entries of this kind are located in the main block diagonal of the adjacency tensor in matrix form, which actually corresponds to the snapshots.

In our general representation, we allow spatial and temporal self-loops (i.e. dynamic edges connecting a node to itself at the same time instant). This kind of edge is represented on the main diagonal of the matrix, just as it would be on an adjacency matrix of a static graph.

Any TVG of the snapshot class can be represented in this straightforward way in our proposed unifying model. Actually, snapshot models are in fact a sub-space of the representable TVGs in our model, making clear that this whole class of snapshot models is rather a subset of the representable TVGs in our model. Further, in snapshot models, each snapshot is formally disconnected from each other (although arguably implicitly connected), since the temporal connections are not explicitly constructed in the snapshot models.

The number of dynamic edges used to represent a TVG of this kind is the same as the number of edges present in the original snapshot-based representation. Therefore, the memory complexity for storing TVGs in our model is the same found on the original snapshot-based representation, which is compatible with the memory complexity discussed in Section 3.5.

Models based on continuous time intervals (CTI)

The class discussed in this subsection includes models that use a presence function defined over continuous time intervals (i.e. t ∈ R + ), such as the continuous time version of TVG proposed by Casteigts et al. [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]. We further assume that the presence function used in such models is constructed in such a way that every time interval (or their union) has a non-zero and finite measure. Although this assumption is not explicitly stated in the original paper, it is consistent In order to represent TVGs based on continuous time intervals in our unifying model, some representations are possible depending on the target application of the model that defines the semantics associated with an edge in the TVG. An example with three possible representations is presented in Figure 10 and each of the these three representations is explained in the following.

If the semantic of a time interval (t a , t b ] associated with an edge e between two nodes u and v is that the edge exists from the beginning of the interval (i.e. from time t a ) until the end of the interval (i.e. until time t b ), it is possible to represent the existence of such an edge by using a mixed dynamic edge. This is consistent with the original semantics, where the edge e exists in the interval delimited by the mixed edge (i.e. from t a until t b ). A concrete example of this first representation is shown comparing Figures 10(a) and 10(b). The edge between nodes 0 and 1 present at the time interval (1, 15] shown in Figure 10(a) is represented by the mixed dynamic edge (0, t 1 , 1, t 15 ) in Figure 10(b). Similarly, the edge between nodes 1 and 2 at the time interval (5, 7] is represented by the mixed dynamic edge (1, t 5 , 2, t 7 ).

In the case an edge is present at different time intervals, we represent this edge by having one mixed edge for each time interval. Further, if the edge between nodes u and v is bidirectional, this edge is represented at each time interval by the pair of edges (u, t a , v, t b ) and (v, t a , u, t b ). Note that once the edges present in the TVG are defined for all time intervals, it is possible to construct the set T of time instants based on the dynamic edges present in the set E. From this, we conclude that the TVGs in this class modeled by continuous time intervals can be represented in our model using only progressive mixed dynamic edges. Figure 11 shows the possible non-zero entries for a TVG with four nodes and three time instants based on the model of continuous time intervals using the first representation we are describing. Clearly from Figure 11, this kind of TVG is a subspace (and therefore a subset) of the TVGs representable by our proposed unifying model. Thus, we conclude that TVGs of this class are particular cases of the TVGs representable in our model.

Even though this first representation by our model carries all information present in the original TVG based on continuous time intervals, it still relies on an assumption that is not explicitly present in this first representation. Namely, this assumption concerns that the time instants present on each mixed dynamic edge represent the time intervals on which the edge exists. Note that the same happens in the original model based on continuous time intervals. For example, using this assumption, a path between nodes 0 and 2 exists at any given time instant during the interval between t 5 and t 7 . To understand that this assumption is made in a manner that does not directly follows as a property of the structure of the TVG, notice that it makes the transitivity of the relation implied by an edge more difficult and cumbersome to determine. This happens because an external processing is needed to verify the presence of the edge (either by the time intervals indicated on the mixed dynamic edge or by the set of intervals on the continuous time model) in order to be able to establish its transitivity to another edge. To establish the existence of a path connecting two nodes, it is necessary to compute the intersections of the time intervals on which each edge exists. The resulting path then exists on the time interval obtained by this intersection. Therefore, the existence of a path connecting nodes in this kind of representation can be non-intuitive and computationally expensive to determine, thus impacting considerations about connectivity, reachability, communicability, and any other property derived from the transitivity of edges in a TVG.

A second representation (Figure 10(c)) comes from the realization that the continuous time

Inria 0 1 2 3 0 1 2 3 0 1 2 3 t0 t1 t2 t0 t1 t2 0 1 2 3 0 1 2 3 0 1 2 3 Mat(A G1 ) = 2
0 0 0 0 0 ⇤ ⇤ ⇤ 0 ⇤ ⇤ ⇤ 0 0 0 0 ⇤ 0 ⇤ ⇤ ⇤ 0 ⇤ ⇤ 0 0 0 0 ⇤ ⇤ 0 ⇤ ⇤ ⇤ 0 ⇤ 0 0 0 0 ⇤ ⇤ ⇤ 0 ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ 0
0 0 0 0 0 0 0 ⇤ 0 ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ 0 ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10(c), where the edge between nodes 0 and 1 is present at instants t 0 , t 5 , t 7 , and t 15 , while the edge between nodes 1 and 2 is present at instants t 5 and t 7 . This representation has the same characteristics we highlighted for the snapshot class of models.

Although the TVG connectivity can be readily determined at each time instant, the snapshots (i.e. time instants) are formally disconnected from each other. Hence, if any sort of connectivity between time instants is to be considered, it has to be stated as an additional assumption, which is not directly encoded in the representation. A third representation (Figure 10(d)) can be derived from the second one (snapshots), by formally placing temporal dynamic edges where the connectivity between successive time instants is desired. In our example, this leads to the representation shown in Figure 10(d), where temporal nodes are used to connect nodes 0 and 1 between time instants t 0 , t 5 , t 7 , and t 15 and to connect nodes 1 and 2 from time instant t 5 to t 7 . This reflects the fact that in the original CTI model the edge (0, 1) was present at the interval (t 0 , t 15 ], while the edge (1, 2) was present at the interval (t 5 , t 7 ]. Figure 12 shows the possible non-zero entries on the matrix form of the adjacency tensor of a TVG of this class using this third representation.

In order to determine the memory complexity of representing a TVG based on continuous time intervals in our proposed unifying model, we state the following proposition, based on the third representation, presented in Figure 10(d Hence, as η mixed dynamic edges are needed in the representation, to fully decompose them into spatial and temporal edges, at most η(3|T | -2) dynamic edges are needed. Expanding and substituting |T | = 2η for the worst case, we have

⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 ⇤ 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 ⇤ 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 ⇤ 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 ⇤ 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 3
η(3|T | -2) = η(6η -2) = 6η 2 -2η.
We therefore conclude that the number of dynamic edges needed is O(η 2 ).

From this, we further conclude that, for a TVG with η continuous time intervals, in our model we have |E| = O(η 2 ). Therefore, the memory complexity of the representation based on continuous time instants is O(η 2 ), which is compatible with the memory complexity discussed in Section 3.5.

Inria

Models based on spatial and temporal edges (STE)

Some models like the one proposed by Kostakos [START_REF] Vassilis | Temporal graphs[END_REF] are based on the idea that a class of links represent instantaneous iterations between distinct nodes while other class represent a waiting state of a given node. These concepts are formalized in our proposed unifying model by spatial and temporal dynamic edges. In our model, these dynamic edges are fully formalized and can be used to make a unambiguous representation of this kind of TVG. Figure 13 depicts the entries that may be non-zero on the matrix form of the adjacency tensor of a TVG of this class having four nodes and three time instants. It is again clear that this class of TVGs can be thus represented as a subset of the TVGs that can be represented by the unifying model we propose. ⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 ⇤ 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 ⇤ 0 0 0 ⇤ 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 ⇤ 0 0 0 ⇤ 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 ⇤ 0 0 0 ⇤ 0 0 0 0 ⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 ⇤ 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 ⇤ 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤

Models based on temporal and mixed edges (TME)

Some works found in the recent literature, such as the one by Kim and Anderson [START_REF] Kim | Temporal node centrality in complex networks[END_REF], loosely suggest the use of edges connecting nodes at different time instants. TVGs of this class can be represented in our model using only temporal and mixed dynamic edges. Figure 14 shows the matrix form of the adjacency tensor of a TVG of this class. It can be seen that this is also a particular case of the TVGs that can be represented using our unifying model. 0 0 0 0 ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 0 ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 0 ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 0 ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 ⇤ ⇤ ⇤ ⇤ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 can represent snapshot models because they support the notion of spatial edges as well as they are mutually able to represent each other. Models based on temporal and mixed edges (TME) are able to represent models based on continuous time intervals (CTI) in a discretized way. Remark that the converse is not true, i.e. models based on CTI are unable to represent models based on TME as they lack the notion of mixed edges. Furthermore, note that models based on TME are unable to represent in all cases models with spatial edges, such as the ones based on snapshots and STE. This is because, although a mixed edge could be seen as a composition of a spatial and a temporal edge, a mixed edge is unable to represent a single spatial edge, thus preventing the representation of these cases.

Overview on the unifying representation of previous models

Overall, we remark that considering the previous classes of TVG models, none is able to represent all others. This basically happens because the kind of edges present in one model not necessarily can be transformed into the kind of edges present in another model or class of models. In contrast, we have shown along this section that all classes of previous TVG models we consider can be represented in the unifying model we propose, whereas these previous TVG models not necessarily are able to represent each other, as shown in Table 1. Additionally, none of the previous TVG models makes use of regressive edges, which could be used in our proposal to intrinsically model cyclic (i.e. periodic) behavior in dynamic networks. Therefore, we highlight that none of the previous analyzed models have all the representation capabilities and thus the Inria

Summary and outlook

In this paper, we have proposed a novel model for representing finite discrete Time-Varying Graphs (TVGs). We have shown that our model is simple, yet flexible and efficient for representation and modeling of dynamic networks. The proposed model preserves the discrete nature of the basic graph abstraction and has algebraic representations similar to the ones used on a regular graph. Moreover, we have also shown that our unifying model has enough expressive power to represent several previous (classes of) models for dynamic networks found in the recent literature, which in general are unable to represent each other, and also to intrinsically represent cyclic (i.e. periodic) behavior of dynamic networks. To further illustrate the flexibility of our model, we remark that our model can also be used to represent time schedules using a TVG. For example, in this case, the nodes can be thought of as locations and mixed edges as the amount of time taken to move between locations. Such representation can model scheduled arrivals and departures in transportation systems allowing, for instance, the evaluation whether a connection is feasible or the delivery time for logistics management.

We have analyzed the proposed model proving that if the TVG nodes can be considered as independent entities at each time instant, the analyzed TVG is isomorphic to a directed static graph. This basic theoretical result has provided the ground for achieving other theoretical results that show that some properties of the analyzed TVG can be inferred from the temporal node representation of that TVG. This is an important set of theoretical results because this allows the use of the isomorphic directed graph as a tool to analyze both the properties of a TVG and the behavior of dynamic processes over a TVG. We have also demonstrated that, for most practical cases, the asymptotic memory complexity of our TVG model is determined by the cardinality of the set of edges. Further, from the basic definition of the model we proposed for representing TVGs, we have derived some basic properties such as communicability and connectivity using only properties that follow directly from the underlying structure of the model, such as the transitivity of the relation induced by the dynamic edges. As a consequence, in contrast to previous works, our model can be used without the need of external assumptions, meaning that all properties are derived from explicit properties of the TVG, in the same way that happens with static graphs.

As future work, we intend to build upon our proposed model, using it to analyze the behavior of dynamic processes over TVGs, such as random walks or diffusion processes, and also to model the dynamics of different networks. Moreover, given the encouraging features shown by our unifying model for representing TVGs, we believe it is promising to further study and explore the potential of this model. In particular, we intend to further investigate the combinational and algebraic properties of this model, as a step forward while aiming at the development of a fundamental theory for TVGs parallel to the existing one for static graphs.

  |V (H)| = |V (K)| and |T (H)| = |T (K)|. From the requirement that a dynamic edge (u, t a , v, t b ) exists in H if and only if the dynamic edge (f (u), g(t a ), f (v), g(t b )) exists in K, it can be seen that two isomorphic TVGs also have the same number of dynamic edges, i.e. |E(H)| = |E(K)|.

Figure 1 :

 1 Figure 1: Native and temporal node representations of an illustrative TVG.

Figure 2 :

 2 Figure 2: Time-variyng graph example.

Figure 3 :

 3 Figure 3: Example of a strongly connected TVG.

Figure 4 :

 4 Figure 4: Closed strongly connected TVG.

Figure 5 :

 5 Figure 5: Closed strongly connected TVG with stronger time constraints.

Figure 6 :

 6 Figure 6: TVG W : Example for algebraic representation.

Figure 7 :

 7 Figure 7: The matrix form of the adjacency tensor of TVG W .

  has 16 × 4 × 3 = 192 entries. Note that the incidence tensor is by construction a sparse tensor, since its dimension is |E(H)| × |V (H)| × |T (H)| and the number of non-zero entries is 2 × |E(H)|.

  e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 e14 e15Mat(C G1 ) =

Theorem 3 . 1

 31 If the set of disconnected nodes and the set of unused time instants are significantly smaller than the set of dynamic edges, then the memory complexity M C (H) for storing a given TVG H is determined by the size of the set of dynamic edges, i.e. M C (H) = Θ(|E(H)|).

Figure 9 :

 9 Figure 9: Snapshot models represented by our unifying TVG model.

  Third representation: Use of temporal and spatial edges.

Figure 10 :

 10 Figure 10: Converting continuous time intervals into a discrete TVG.

  ), which uses the largest number of dynamic edges: Proposition 4.1 A TVG based on continuous time intervals with n nodes, m edges, and η

Figure 12 :Proof 4 . 1

 1241 Figure 12: The third representation of TVGs based on continuous time intervals.

Figure 13 :

 13 Figure 13: Representation of TVGs based on spatial and temporal edges.

Figure 14 :

 14 Figure 14: Representation of TVGs based on and mixed edges.

  Theorem 2.5 If two spatial or mixed edges in a TVG H are incident to the same node, then their projections on the aggregate graph are adjacent. Let e 1 , e 2 ∈ E(H) be a pair of spatial or mixed dynamic edges in TVG H, such that both are incident to a given node v. Since these edges are spatial or mixed dynamic edges, they have distinct origin and destination nodes. Hence, without loss of generality, we can define e 1 = (u, t a , v, t b ) and e 2 = (v, t c , w, t d ), where u = v and v = w are nodes in TVG H and t a , t b , t c , t d ∈ T (H) are time instants. Applying the projection π used to get the aggregate graph (see Section 2.5) to the edges, we get π(e 1 ) = (u, v) and π(e 2 ) = (v, w). Since u = v and v = w, (u, v) and (v, w) are two distinct directed edges, and since both are incident to node v, it follows that they are adjacent edges in Agg(H), the aggregated graph of the TVG H.

	Proof 2.6

6

  An alternating sequence W of temporal nodes and dynamic edges in a TVG H is a walk on H if and only if there is a corresponding walk G W in the temporal node representation of H. As stated in Section 2.4, for the temporal node representation g(H) of the TVG H there is a bijective function

	Proof 2.7

  and T (W ) ⊆ T (H), it follows that the trail W is a sub-TVG of H.

Theorem 2.8 A walk H W on H is a trail on H if and only if there is a corresponding trail G W on g(H).

  The complete expression of the memory complexity for a given TVG H is M C (H) = Θ(|V N (H)| + |T N (H)| + |E(H)|). It follows from the proof of Theorem 3.1 that the formal and complete expression of the lower bound memory complexity for storing a given TVG H is M C (H) = Ω(|V N (H)| + |T N (H)| + |E(H)|), where V N (H) its set of disconnected nodes, T N (H) its set of unused time instants, and E(H) the set of dynamic edges, while the upper bound is M C (H) = Ω(|V N (H)| + |T N (H)| + |E(H)|). We therefore conclude that complete form of the memory complexity is M C (H) = Θ(|V N (H)| + |T N (H)| + |E(H)|). in most practical cases the amount of disconnected nodes and unused time instants is significantly smaller than the number of dynamic edges (i.e., |V N (H)| + |T N (H)| |E(H)|), we can conclude that the expected amount of memory needed to store a representation of a given TVG H is determined by the size of the set of dynamic edges |E(H)|, i.e. M C (H) = Θ(|E(H)|) as states Theorem 3.1. Furthermore, any given TVG H for most practical applications can typically be expected to be sparse, i.e. the number of dynamic edges is significantly smaller than the squared number of temporal nodes (|E(H)| |V T (H)| 2 ), thus allowing its storage in a compact form, similar to the compressed forms used for sparse matrices [BBC + 94].

		we finally conclude that M C (H) =
	Θ(|E(H)|), if |V N (H)| + |T N (H)|	|E(H)|.
	Corollary 3.1 Proof 3.3 Since

  Figure 11: The first representation of TVGs based on continuous time intervals. intervals model is in fact a continuos form of the snapshot model, in which edges are present at infinite (uncountable) time instants. Therefore, a natural way to represent the CTI model in a discrete form is to have the time instants set T formed by the beginning and end instants of each interval present on the CTI model, and then placing the corresponding edge at each time instant for which an edge is present in the CTI model. The result of this is a snapshot representation of the CTI model, as shown in Figure

	3
	7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5

  Table1shows a representation map that indicates if a (class of) TVG model(s) is able to represent another (class of) TVG model(s). We compare the unifying representation model we propose with the models based on (i) snapshots, (ii) continuous time intervals (CTI), (iii) spatial and

	Mat(A G1 ) =	2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4	0 1 2 3 0 1 2 3 0 1 2	t0 t1 t2
			3
		t0 0 1 2 3 0 1 2 3 0 1 2 3 t1 t2

Table 1 :

 1 Representation map between TVG models: An entry is checked if the (class of) model(s) in the row is able to represent the (class of) model(s) in the column.

	Snapshots	CTI	STE	TME	Unifying model
	Snapshots
	CTI
	STE
	TME
	Unifying model
	same expressive power of our proposed unifying model for TVGs.

RR n°8466

This is in fact a slight abuse of notation, since (f -1 (w) and (f -1 (z) are ordered pairs. The formally correct notation is (π 1 (f -1 (w)), π

(f -1 (w)), π 1 (f -1 (z)), π 2 (f -1 (z))).Inria

Acknowledgment

This work was partially funded by the Brazilian funding agencies CAPES, CNPq, and FAPERJ as well as the Brazilian Ministry of Science, Technology, and Innovation (MCTI).