Approximate lumpability for Markovian agent-based models using local symmetries

February 12, 2019
We study a Markovian agent-based model (MABM). Each agent is endowed with a local state that changes over time as the agent interacts with its neighbours. The neighbourhood structure is given by a graph.  Examples of such systems include epidemic processes, percolation, peer-to-peer systems etc. In a recent paper [Simon et al. 2011], the automorphisms of the underlying graph were used to generate a lumpable partition of the joint state space ensuring Markovianness of the lumped process for binary dynamics. However, many large random graphs tend to become asymmetric rendering the automorphism-based lumping approach ineffective as a tool of model reduction. In order to mitigate this problem, we propose a lumping method based on a notion of local symmetry, which compares only local neighbourhoods of vertices. Since local symmetry only ensures approximate lumpability, we quantify the approximation error by means of Kullback-Leibler divergence rate between the original Markov chain and a lifted Markov chain. We prove the approximation error decreases monotonically. The connections to fibrations of graphs are also discussed. (Joint work with Arnab Auddy, Yann Disser and Heinz Koeppl)