The many faces of graph dynamics

The topological structure of complex networks has fascinated researchers for several decades, resulting in the discovery of many universal properties and reoccurring characteristics of different kinds of networks. However, much less is known today about the network dynamics: indeed, complex networks in reality are not static, but rather dynamically evolve over time.

Our work is motivated by the empirical observation that network evolution patterns seem far from random, but exhibit structure. Moreover, the specific patterns appear to depend on the network type, contradicting the existence of a “one fits it all” model. However, we still lack observables to quantify these intuitions, as well as metrics to compare graph evolutions. Such observables and metrics are needed for extrapolating or predicting evolutions, as well as for interpolating graph evolutions.

To explore the many faces of graph dynamics and to quantify temporal changes, we propose to build upon the concept of centrality, a measure of node importance in a network. In particular, we introduce the notion of centrality distance, a natural similarity measure for two graphs which depends on a given centrality, characterizing the graph type. Intuitively, centrality distances reflect the extent to which node roles are different or, in case of dynamic graphs, have changed over time, between two graphs.

References :
Y. A. Pignolet, M. Roy, S. Schmid and G. Trédan. « The many faces of graph dynamics ». In : Journal of Statistical Mechanics : Theory and Experiment 2017 (juin 2017).  https://hal.archives- ouvertes.fr/hal-01559708
M. Roy, S. Schmid and G. Trédan. « Modeling and Measuring Graph Similarity : The Case for Centrality Distance ». In : FOMC 2014, 10th ACM International Workshop on Foundations of Mobile Computing.
https://hal.archives-ouvertes.fr/hal-01010901