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.

 

Random walks and diffusion on networks
Naoki Masuda, Mason A. Porter, Renaud Lambiotte

Physics Reports
Volumes 716–717, 22 November 2017, Pages 1-58

Source: www.sciencedirect.com

The relationship between the structure and dynamics of a network is key to understanding the behavior of complex systems. A new analysis shows how network optimization, whether designed or evolved, can lead to collective dynamics that depend sensitively on the structure of the network.

 

Sensitive Dependence of Optimal Network Dynamics on Network Structure

Takashi Nishikawa, Jie Sun, and Adilson E. Motter
Phys. Rev. X 7, 041044

Source: journals.aps.org

In practical terms, controlling a network requires manipulating a large number of nodes with a comparatively small number of external inputs, a process that is facilitated by paths that broadcast the influence of the (directly-controlled) driver nodes to the rest of the network. Recent work has shown that surprisingly, temporal networks can enjoy tremendous control advantages over their static counterparts despite the fact that in temporal networks such paths are seldom instantaneously available. To understand the underlying reasons, here we systematically analyze the scaling behavior of a key control cost for temporal networks–the control energy. We show that the energy costs of controlling temporal networks are determined solely by the spectral properties of an “effective” Gramian matrix, analogous to the static network case. Surprisingly, we find that this scaling is largely dictated by the first and the last network snapshot in the temporal sequence, independent of the number of intervening snapshots, the initial and final states, and the number of driver nodes. Our results uncover the intrinsic laws governing why and when temporal networks save considerable control energy over their static counterparts.

 

Control energy scaling in temporal networks
Aming Li, Sean P. Cornelius, Yang-Yu Liu, Long Wang, Albert-László Barabási

Source: arxiv.org

Predictive models for human mobility have important applications in many fields including traffic control, ubiquitous computing, and contextual advertisement. The predictive performance of models in literature varies quite broadly, from over 90% to under 40%. In this work we study which underlying factors – in terms of modeling approaches and spatio-temporal characteristics of the data sources – have resulted in this remarkably broad span of performance reported in the literature. Specifically we investigate which factors influence the accuracy of next-place prediction, using a high-precision location dataset of more than 400 users observed for periods between 3 months and one year. We show that it is much easier to achieve high accuracy when predicting the time-bin location than when predicting the next place. Moreover, we demonstrate how the temporal and spatial resolution of the data have strong influence on the accuracy of prediction. Finally we reveal that the exploration of new locations is an important factor in human mobility, and we measure that on average 20-25% of transitions are to new places, and approx. 70% of locations are visited only once. We discuss how these mechanisms are important factors limiting our ability to predict human mobility.

 

Understanding predictability and exploration in human mobility
Andrea Cuttone, Sune Lehmann and Marta C. González
EPJ Data Science20187:2
https://doi.org/10.1140/epjds/s13688-017-0129-1

Source: epjdatascience.springeropen.com