MBI Videos

Approximate lumpability for Markovian agent-based models using local symmetries

  • video photo
    Wasiur KhudaBukhsh

    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)


View Videos By