A Unifying Model for Representing Time-Varying Graphs

Klaus Wehmuth (1) , Artur Ziviani (1) , Eric Fleury (2)

1 LNCC / MCT - Laboratorio Nacional de Computação Cientifica [Rio de Janeiro]
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach

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.

Nous proposons un modèle (TVG pour \emph{Time-Varying Graphs}) pour représenter les graphes dynamiques (\emph{i.e.}, des graphes susceptibles d'évoluer au cours du temps). Nous montrons qu elles définitionsclefs comme le degré, la notion de chemin, de connectivité sont prise en compte par ce modèle. Une analyse de la complexité des structures de données nécessaire à la représentation de ce modèle montre que la complexité asymptotique est en $O(m)$ (cardinalité du nombre d'arêtes du graphe dynamique). Si les sommets d'un TVG peuvent être considérés comme des entités indépendantes à chaque instant, alors on démontre que le graphe TVG est isomorphe à un graphe orienté static. Notre modèle permet de représenter et de prendre en compte les différentes propositions existantes qui n'étaient pas en mesure de se représenter les unes les autres.

Mots clés: dynamic networks; temporal networks; graphs; dynamic graphs; complex networks; network science

Domaines: Informatique mobile; Réseaux sociaux et d'information [cs.SI]; Mathématique discrète [cs.DM]

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