We study random walks with stochastic resetting to the initial position on arbitrary networks. We obtain the stationary probability distribution as well as the mean and global first passage times, which allow us to characterize the effect of resetting on the capacity of a random walker to reach a particular target or to explore a finite network. We apply the results to rings, Cayley trees, and random and complex networks. Our formalism holds for undirected networks and can be implemented from the spectral properties of the random walk without resetting, providing a tool to analyze the search efficiency in different structures with the small-world property or communities. In this way, we extend the study of resetting processes to the domain of networks.

We introduce a formalism of fractional diffusion on networks based on a fractional Laplacian matrix that can be constructed directly from the eigenvalues and eigenvectors of the Laplacian matrix. This fractional approach allows random walks with long-range dynamics providing a general framework for anomalous diffusion and navigation, and inducing dynamically the small-world property on any network. We obtained exact results for the stationary probability distribution, the average fractional return probability, and a global time, showing that the efficiency to navigate the network is greater if we use a fractional random walk in comparison to a normal random walk. For the case of a ring, we obtain exact analytical results showing that the fractional transition and return probabilities follow a long-range power-law decay, leading to the emergence of Lévy flights on networks. Our general fractional diffusion formalism applies to regular, random, and complex networks and can be implemented from the spectral properties of the Laplacian matrix, providing an important tool to analyze anomalous diffusion on networks.

We introduce a strategy of navigation in undirected networks, including regular, random, and complex networks, that is inspired by L\'evy random walks, generalizing previous navigation rules. We obtained exact expressions for the stationary probability distribution, the occupation probability, the mean first passage time, and the average time to reach a node on the network. We found that the long-range navigation using the L\'evy random walk strategy, compared with the normal random walk strategy, is more efficient at reducing the time to cover the network. The dynamical effect of using the L\'evy walk strategy is to transform a large-world network into a small world. Our exact results provide a general framework that connects two important fields: L\'evy navigation strategies and dynamics on complex networks.

Click on the title to browse this book

We analyze the massive data set of more than one billion taxi trips in New York City, from January 2009 to December 2015. With these records of seven years, we generate an origin-destination matrix that has information of a vast number of trips. The mobility and flow of taxis can be described as a directed weighted network that connects different zones of high demand for taxis. This network has in and out degrees that follow a stretched exponential and a power law with an exponential cutoff distributions, respectively. Using the origin-destination matrix, we obtain a rank, called "OD rank”, analogous to the page rank of Google, that gives the more relevant places in New York City in terms of taxi trips. We introduced a model that captures the local and global dynamics that agrees with the data. Considering the taxi trips as a proxy of human mobility in cities, it might be possible that the long-range mobility found for New York City would be a general feature in other large cities around the world.

In this article, we present a survey of different types of random walk models with local and non-local transitions on undirected weighted networks. We present a general approach by defining the dynamics as a discrete-time Markovian process with transition probabilities expressed in terms of a symmetric matrix of weights. In the first part, we describe the matrices of weights that define local random walk dynamics like the normal random walk, biased random walks and preferential navigation, random walks in the context of digital image processing and maximum entropy random walks. In addition, we explore non-local random walks, like Lévy flights on networks, fractional transport through the new formalism of fractional graph Laplacians, and applications in the context of human mobility. Explicit relations for the stationary probability distribution, the mean first passage time and global times to characterize random walks are obtained in terms of the elements of the matrix of weights and its respective eigenvalues and eigenvectors. Finally, we apply the results to the analysis of particular local and non-local random walk dynamics, and we discuss their capacity to explore several types of networks. Our results allow us to study and compare the global dynamics of different types of random walk models.