The many faces of graph dynamics
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- A survey of graph edit distance
- Complex graphs and networks
- Complex networks: structure and dynamics
- Emergence of Scaling in Random Networks
- Empirical Analysis of an Evolving Social Network
- Generating Random Regular Graphs Quickly
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- Network analysis. Methodological foundations.
- Random graph models of social networks
- Snapshot centrality indices in dynamic FIFO networks
- Transactions on Computational Systems Biology III
Cited in
(4)
This page was built for publication: The many faces of graph dynamics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3303089)
