Random walks and diffusion on networks

Naoki Masuda, Mason A. Porter, Renaud Lambiotte

Research output: Contribution to journalArticlepeer-review

3 Downloads (Pure)


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
Publication statusPublished - 22 Nov 2017
Externally publishedYes


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


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

Cite this