This paper describes a formalization of agent-based models (ABMs) as random walks on regular graphs and relates the symmetry group of those graphs to a coarse-graining of the ABM that is still Markovian. An ABM in which $N$ agents can be in $delta$ d
ifferent states leads to a Markov chain with $delta^N$ states. In ABMs with a sequential update scheme by which one agent is chosen to update its state at a time, transitions are only allowed between system configurations that differ with respect to a single agent. This characterizes ABMs as random walks on regular graphs. The non-trivial automorphisms of those graphs make visible the dynamical symmetries that an ABM gives rise to because sets of micro configurations can be interchanged without changing the probability structure of the random walk. This allows for a systematic loss-less reduction of the state space of the model.
For Agent Based Models, in particular the Voter Model (VM), a general framework of aggregation is developed which exploits the symmetries of the agent network $G$. Depending on the symmetry group $Aut_{omega} (N)$ of the weighted agent network, certa
in ensembles of agent configurations can be interchanged without affecting the dynamical properties of the VM. These configurations can be aggregated into the same macro state and the dynamical process projected onto these states is, contrary to the general case, still a Markov chain. The method facilitates the analysis of the relation between microscopic processes and a their aggregation to a macroscopic level of description and informs about the complexity of a system introduced by heterogeneous interaction relations. In some cases the macro chain is solvable.
