A New Model for Time-Varying Graphs

International audienceWe propose a new model for finite discrete time-varying graphs (TVGs), suitable for the representation of dynamic networks, for instance. The model we propose is based on the concept that in this class of TVGs there is typically a finite number of nodes and also a finite number of time instants. In this context, roughly speaking, an edge is able to connect any pair of nodes in any pair of time instants. This leads to the conception that in this environment an edge should be represented by an ordered quadruple of the form $(u, t_p, v, t_q)$, where $u$ and $v$ are nodes and $t_p$ and $t_q$ are time instants. Building upon this concept, we propose a new model that defines a TVG as an object $G_d = (V, E, T, \Phi)$, where $V$ is the set of nodes, $T$ is the set of time instants on which the TVG is defined, $E \subseteq V \times T \times V \times T$ is the set of edges in the TVG and $\Phi$ is a function that assigns a weight to each edge. In this on-going work, we show how key concepts such as degrees, journeys, distance, connectivity, are handled in this environment and also study the data structures used for the representation of dynamic networks built following our model. Moreover, we proof that when the TVG nodes can be considered as independent entities in each time instant, the analyzed TVG is isomorphic to a directed static graph. The basic idea behind the proof is hinted by the fact that if the nodes are elements of $V \times T$, an edge in the TVG could be seen as a pair $((u,t_p), (v,t_q))$, which in this case would represent a directed edge from node $(u, t_p)$ to node $(v,t_q)$, reducing the TVG to a simple directed graph. This is an important theoretical result because this allows the application of known results from the theory of directed graphs in the context of dynamic networks, either in a straightforward way when the nodes can be treated as independent in each time instant, or as a means for adapting known results to the more general TVG environment. In order to ascertain the generality of our proposed model, we show it can be used to represent several previous cases of dynamic networks found in the recent literature, which in general are unable to represent each other