Random walks and diffusion on networks

• DOI: 10.1016/j.physrep.2017.07.007
• Publication Date: 2017-08-31T21:48:05Z
• Authors: Naoki Masuda; Mason A. Porter; Renaud Lambiotte
• Keywords: PageRank; Random walker algorithm

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