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 metadatas

https://hal.inria.fr/hal-00941622
Contributor : Eric Fleury <>
Submitted on : Tuesday, February 4, 2014 - 10:14:31 AM
Last modification on : Wednesday, January 23, 2019 - 7:48:12 PM
Long-term archiving on : Sunday, April 9, 2017 - 7:08:18 AM

File

RR-8466.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00941622, version 1

Collections

Citation

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

Share

Metrics

Record views

73

Files downloads

109