  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 paper 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,
this paper suggests 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 (non-anonymous) node roles are different or, in
case of dynamic graphs, have changed over time, between two graphs.
  We evaluate the centrality distance approach for five evolutionary models and
seven real-world social and physical networks. Our results empirically show the
usefulness of centrality distances for characterizing graph dynamics compared
to a null-model of random evolution, and highlight the differences between the
considered scenarios. Interestingly, our approach allows us to compare the
dynamics of very different networks, in terms of scale and evolution speed.
