  Pathways of diffusion observed in real-world systems often require stochastic
processes going beyond first-order Markov models, as implicitly assumed in
network theory. In this work, we focus on second-order Markov models, and
derive an analytical expression for the effect of memory on the spectral gap
and thus, equivalently, on the characteristic time needed for the stochastic
process to asymptotically reach equilibrium. Perturbation analysis shows that
standard first-order Markov models can either overestimate or underestimate the
diffusion rate of flows across the modular structure of a system captured by a
second-order Markov network. We test the theoretical predictions on a toy
example and on numerical data, and discuss their implications for network
theory, in particular in the case of temporal or multiplex networks.
