Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.physrep.2017.07.007 | Physics Reports |
Keywords | Field | DocType |
Random walk,Network,Diffusion,Markov chain,Point process | Statistical physics,PageRank,Random graph,Ranking,Quantum mechanics,Random walk,Point process,Markov chain,Stochastic process,Sampling (statistics),Physics | Journal |
Volume | ISSN | Citations |
716 | 0370-1573 | 14 |
PageRank | References | Authors |
0.70 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Naoki Masuda | 1 | 84 | 11.38 |
| Mason A. Porter | 2 | 748 | 66.14 |
| Renaud Lambiotte | 3 | 920 | 64.98 |