TY - JOUR

T1 - Random walks and diffusion on networks

AU - Masuda, Naoki

AU - Porter, Mason A.

AU - Lambiotte, Renaud

N1 - Publisher Copyright:
© 2017 The Author(s)

PY - 2017/11/22

Y1 - 2017/11/22

N2 - 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.

AB - 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.

KW - Diffusion

KW - Markov chain

KW - Network

KW - Point process

KW - Random walk

UR - http://www.scopus.com/inward/record.url?scp=85054407686&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054407686&partnerID=8YFLogxK

U2 - 10.1016/j.physrep.2017.07.007

DO - 10.1016/j.physrep.2017.07.007

M3 - Review article

AN - SCOPUS:85054407686

SN - 0370-1573

VL - 716-717

SP - 1

EP - 58

JO - Physics Reports

JF - Physics Reports

ER -