Skip to Main content Skip to Navigation

A Unifying Model for Representing Time-Varying Graphs

Klaus Wehmuth 1 Artur Ziviani 1, * Eric Fleury 2, *
* Corresponding author
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : 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.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Eric Fleury Connect in order to contact the contributor
Submitted on : Friday, February 14, 2014 - 9:34:18 AM
Last modification on : Thursday, October 21, 2021 - 5:08:17 AM
Long-term archiving on: : Sunday, April 9, 2017 - 10:48:20 AM


Files produced by the author(s)


  • HAL Id : hal-00941622, version 2
  • ARXIV : 1402.3488


Klaus Wehmuth, Artur Ziviani, Eric Fleury. A Unifying Model for Representing Time-Varying Graphs. [Research Report] RR-8466, INRIA. 2014, pp.38. ⟨hal-00941622v2⟩



Les métriques sont temporairement indisponibles