Journal article
Random walks and diffusion on networks
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 1.6MB, Terms of use)
-
- Publisher copy:
- 10.1016/j.physrep.2017.07.007
Authors
- Publisher:
- Elsevier
- Journal:
- Physics Reports More from this journal
- Publication date:
- 2017-08-01
- Acceptance date:
- 2017-07-25
- DOI:
- Keywords:
- Pubs id:
-
pubs:729443
- UUID:
-
uuid:934c5ca5-4b5f-492a-8399-9ed9017615bd
- Local pid:
-
pubs:729443
- Source identifiers:
-
729443
- Deposit date:
-
2017-09-22
- ARK identifier:
Terms of use
- Copyright holder:
- Lambiotte et al
- Copyright date:
- 2017
- Notes:
- © 2017 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). Corrections to this article are available at: https://doi.org/10.1016/j.physrep.2018.06.002 and https://doi.org/10.1016/j.physrep.2020.02.005
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record