The exact treatment of Markovian models on complex networks requires knowledge of probability distributions expo- nentially large in the number of nodes n. Mean-field approximations provide an effective reduction in complexity of the models, requiring only a number of phase space variables polynomial in system size. However, this comes at the cost of losing accuracy close to critical points in the systems dynamics and an inability to capture correlations in the system. In this talk, we introduce a tunable approximation scheme for Markovian spreading models on networks based on matrix product states (MPSs). By controlling the bond dimensions of the MPS, we can investigate the effective dimensional- ity needed to accurately represent the exact 2n dimensional steady-state distribution. We introduce the entanglement entropy as a measure of the compressibility of the system and find that it peaks just after the phase transition on the disordered side, in line with the intuition that more complex states are at the ’edge of chaos’. The MPS provides a systematic way to tune the accuracy of the approximation by reducing the dimensionality of the systems state vector, leading to an improvement over second-order mean-field approximations for sufficiently large bond dimensions.