Increasing computational power allows for the description and prediction of natural processes by modelling its smallest-scale interactions, recreating natural phenomena in a bottom-up fashion. Two classes of such approaches, which are especially pertinent for modelling spatio-temporal processes, are cellular automata (CAs) and their topological extension, network automata (NAs). The simplest types of CAs and NAs are well studied, but for these models to acquire the status of a strong scientific paradigm, they must allow for simple model extensions, whilst at the same time remaining methodologically robust. We will extend these computational models by introducing “spatial heterogeneity”, which includes “rule heterogeneity” and “topological heterogeneity”. The former translates to extending the model in such a way that the set of rules determining the microscopic dynamics, and therefore the emergent process, must no longer be the same on every spatially distinct region. The latter, which is exclusive to NAs, translates to allowing different types of connections between nodes. In both cases, a mathematical framework for these heterogeneities as well as a methodological enquiry into their effect on model stability, quantified by discrete extensions of the Lyapunov exponent, are at the core of this proposal. In a final stage, we will mobilize these models and the newly developed analytical techniques in two applications: epidemiology and opinion dynamics.