Random walks and diffusion on networks

Naoki Masuda*, Mason A. Porter, Renaud Lambiotte

*Corresponding author for this work

Research output: Contribution to journalReview article (Academic Journal)

120 Citations (Scopus)
470 Downloads (Pure)

Abstract

Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.

Original languageEnglish
Pages (from-to)1-58
Number of pages58
JournalPhysics Reports
Volume716-717
Early online date31 Aug 2017
DOIs
Publication statusPublished - 22 Nov 2017

Keywords

  • Random walk
  • Network
  • Diffusion
  • Markov chain
  • Point process

Fingerprint Dive into the research topics of 'Random walks and diffusion on networks'. Together they form a unique fingerprint.

  • Cite this

    Masuda, N., Porter, M. A., & Lambiotte, R. (2017). Random walks and diffusion on networks. Physics Reports, 716-717, 1-58. https://doi.org/10.1016/j.physrep.2017.07.007