A General Model of Dynamics on Networks with Graph Automorphism Lumping

In this paper we introduce a general Markov chain model of dynamical processes on networks. In this model, nodes in the network can adopt a finite number of states and transitions can occur that involve multiple nodes changing state at once. The rules that govern transitions only depend on measures related to the state and structure of the network and not on the particular nodes involved. We prove that symmetries of the network can be used to lump equivalent states in state-space. We illustrate how several examples of well-known dynamical processes on networks correspond to particular cases of our general model. This work connects a wide range of models specified in terms of node-based dynamical rules to their exact continuous-time Markov chain formulation