Taxonomy of Dynamic Graphs

This paper is a survey of different families of dynamic graphs, and of the impact that these simple dynamics have on the overall topology of the graph. It provides a number of naturally occurring update rules, possible extensions, and explicit limit distributions. It furthermore offers a classification of design considerations, both at a local and global scale, and provides an in-depth analysis of the convergence rate of several models.