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 : —Graph-based models form a fundamental aspect of data representation in Data Sciences and play a key role in modeling complex networked systems. In particular, recently there is an ever-increasing interest in modeling dynamic complex networks, i.e. networks in which the topological structure (nodes and edges) may vary over time. In this context, we propose a novel model for representing finite discrete Time-Varying Graphs (TVGs), which are typically used to model dynamic complex networked systems. We analyze the data structures built from our proposed model and demonstrate that, for most practical cases, the asymptotic memory complexity of our model is in the order of the cardinality of the set of edges. Further, we show that our proposal is an unifying model that 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. We thus believe our unifying model for TVGs is a step forward in the theoretical foundations for data analysis of complex networked systems.
Document type :
Conference papers
Complete list of metadatas

Cited literature [36 references]  Display  Hide  Download

https://hal.inria.fr/hal-01270367
Contributor : Eric Fleury <>
Submitted on : Thursday, February 11, 2016 - 4:21:54 PM
Last modification on : Wednesday, January 23, 2019 - 7:48:12 PM

Links full text

Identifiers

Citation

Klaus Wehmuth, Artur Ziviani, Eric Fleury. A unifying model for representing time-varying graphs. IEEE International Conference on Data Science and Advanced Analytics. DSAA'2015, Oct 2015, Paris, France. ⟨10.1109/DSAA.2015.7344810⟩. ⟨hal-01270367⟩

Share

Metrics

Record views

224