Litterature on Dynamic graph theory

Question

I was wondering if anyone knows any good articles or papers or books on graph theory that deals with changing graphs and not just static ones.

So far I've only found qualitative descriptions of developing a dynamic graph theory and no actual derivations.

Particularly I'm wondering about dynamical systems represented as graphs.

Any help would be appreciated and thanks in advanced.

Answer 1

I would recommend reading "Universal Resilience Patterns in Complex Networks" https://www.nature.com/articles/nature16948 It focuses on network stability as parameters change and trigger bifurcations. If you are interested, I have also written up some notes on this paper and posted them here: https://logancollinsblog.com/2017/11/26/notes-on-universal-resilience-patterns-in-complex-networks-gao-et-al-2016/

Answer 2

Since this question has been posted, there have been many works in this area. Many of them are quite empirical, but let me mention the following more mathematical works:

• a nice algorithmic-oriented introduction to the field, that surveys various approaches and sees temporal graphs mostly as sequences of graphs over time.

• some works on computational complexity of time-varying graphs, showing that some dynamics families (similar to graph families) may be defined that induce different computational complexity classes. They study many important algorithmic problem, in particular (but not only) reachability and path-related ones.

• some algebraic approaches defining semi-rings on temporal networks, which make it easy to compute their key (temporal and structural) properties, without resorting to the usual time-slicing approach.

• our work on Stream Graphs and Link Streams focusing on fine-grained dynamics of links and nodes. Its key feature is to see graphs as special cases of stream graphs, when there is no dynamics. It extends the basics of graph theory (like density, paths, or cliques, e.g.) in a way consistent with graph concepts.

There are plenty of other references that would be worth mentioning, of course. But I think these four already provide a representative panel of modern approaches to dynamic graphs, with mathematical grounds.