Skip Navigation

Effect of memory on the dynamics of random walks on networks

  1. Vsevolod Salnikov
  1. naXys, University of Namur, Rempart de la Vierge 8, 5000 Namur, Belgium
  1. Corresponding author. E-mail: renaud.lambiotte{at}unamur.be
  1. Martin Rosvall
  1. Integrated Science Lab, Department of Physics, Umeå University, SE-901 87 Umeå, Sweden
  1. Edited by: Mason Porter

  • Received January 3, 2014.
  • Accepted April 23, 2014.

Abstract

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.

Key words

| Table of Contents

This Article

  1. jcomplexnetw 3 (2): 177-188. doi: 10.1093/comnet/cnu017
  1. All Versions of this Article:
    1. cnu017v1
    2. 3/2/177 most recent

Classifications

Share

  1. Email this article

Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.