  This paper is centered on covariant dynamics on unimodular random graphs and
random networks, namely maps from the set of vertices to itself which are
preserved by graph or network isomorphisms. Such dynamics are referred to as
vertex-shifts here. The first result of the paper is a classification of
vertex-shifts on unimodular random networks. Each such vertex-shift partitions
the vertices into a collection of connected components and foils. The latter
are discrete analogues the stable manifold of the dynamics. The classification
is based on the cardinality of the connected components and foils. Up to an
event of zero probability, there are three classes of foliations in a connected
component: F/F (with finitely many finite foils), I/F (infinitely many finite
foils), and I/I (infinitely many infinite foils). An infinite connected
component of the graph of a vertex-shift on a random network forms an infinite
tree with one selected end which is referred to as an Eternal Family Tree. Such
trees can be seen as stochastic extensions of branching processes. Unimodular
Eternal Family Trees can be seen as extensions of critical branching processes.
The class of offspring-invariant Eternal Family Trees, which is introduced in
the paper, allows one to analyze dynamics on networks which are not necessarily
unimodular. These can be seen as extensions of non-necessarily critical
branching processes. Several construction techniques of Eternal Family Trees
are proposed, like the joining of trees or moving the root to a far descendant.
Eternal Galton-Watson Trees and Eternal Multi-type Galton-Watson Trees are also
introduced as special cases of Eternal Family Trees satisfying additional
independence properties. These examples allow one to show that the results on
Eternal Family Trees unify and extend to the dependent case several well known
theorems of the literature on branching processes.
