A unifying model for representing time-varying graphs

Klaus Wehmuth 1 Artur Ziviani 1 Eric Fleury 2, *
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
IEEE International Conference on Data Science and Advanced Analytics. DSAA'2015, Oct 2015, Paris, France. 2015, 〈10.1109/DSAA.2015.7344810〉
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01270367
Contributeur : Eric Fleury <>
Soumis le : jeudi 11 février 2016 - 16:21:54
Dernière modification le : jeudi 12 juillet 2018 - 01:14:04

Lien texte intégral

Identifiants

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. 2015, 〈10.1109/DSAA.2015.7344810〉. 〈hal-01270367〉

Partager

Métriques

Consultations de la notice

178