Mean encounter times for multiple random walkers on networks

Stochastic Compartment Model with Mortality and Its Application to Epidemic Spreading in Complex Networks

We study epidemic spreading in complex networks by a multiple random walker approach. Each walker performs an independent simple Markovian random walk on a complex undirected (ergodic) random graph where we focus on the Barabási-Albert (BA), Erdös-Rényi (ER), and Watts-Strogatz (WS) types. Both walkers and nodes can be either susceptible (S) or infected and infectious (I), representing their state of health. Susceptible nodes may be infected by visits of infected walkers, and susceptible walkers may be infected by visiting infected nodes. No direct transmission of the disease among walkers (or among nodes) is possible. This model mimics a large class of diseases such as Dengue and Malaria with the transmission of the disease via vectors (mosquitoes). Infected walkers may die during the time span of their infection, introducing an additional compartment D of dead walkers. Contrary to the walkers, there is no mortality of infected nodes. Infected nodes always recover from their infection after a random finite time span. This assumption is based on the observation that infectious vectors (mosquitoes) are not ill and do not die from the infection. The infectious time spans of nodes and walkers, and the survival times of infected walkers, are represented by independent random variables. We derive stochastic evolution equations for the mean-field compartmental populations with the mortality of walkers and delayed transitions among the compartments. From linear stability analysis, we derive the basic reproduction numbers RM,R0 with and without mortality, respectively, and prove that RM1, the healthy state is unstable, whereas for zero mortality, a stable endemic equilibrium exists (independent of the initial conditions), which we obtained explicitly. We observed that the solutions of the random walk simulations in the considered networks agree well with the mean-field solutions for strongly connected graph topologies, whereas less well for weakly connected structures and for diseases with high mortality. Our model has applications beyond epidemic dynamics, for instance in the kinetics of chemical reactions, the propagation of contaminants, wood fires, and others.

First encounters on Watts-Strogatz networks and Barabási-Albert networks

The Watts-Strogatz networks are important models that interpolate between regular lattices and random graphs, and Barabási-Albert networks are famous models that explain the origin of the scale-free networks. Here, we consider the first encounters between two particles (e.g., prey A and predator B) embedded in the Watts-Strogatz networks and the Barabási-Albert networks. We address numerically the mean first-encounter time (MFET) while the two particles are moving and the mean first-passage time (MFPT) while the prey is fixed, aiming at uncovering the impact of the prey's motion on the encounter time, and the conditions where the motion of the prey would accelerate (or slow) the encounter between the two particles. Different initial conditions are considered. In the case where the two particles start independently from sites that are selected randomly from the stationary distribution, on the Barabási-Albert networks, the MFET is far less than the MFPT, and the impact of prey's motion on the encounter time is enormous, whereas, on the Watts-Strogatz networks (including Erdős-Rényi random networks), the MFET is about 0.5-1 times the MFPT, and the impact of prey's motion on the encounter time is relatively small. We also consider the case where prey A starts from a fixed site and the predator starts from a randomly drawn site and present the conditions where the motion of the prey would accelerate (or slow) the encounter between the two particles. The relation between the MFET (or MFPT) and the average path length is also discussed.

Optimal exploration of random walks with local bias on networks

We propose local-biased random walks on general networks where a Markovian walker is defined by different types of biases in each node to establish transitions to its neighbors depending on their degrees. For this ergodic dynamics, we explore the capacity of the random walker to visit all the nodes characterized by a global mean first passage time. This quantity is calculated using eigenvalues and eigenvectors of the transition matrix that defines the dynamics. In the first part, we illustrate how our framework leads to optimal exploration for small-size graphs through the analysis of all the possible bias configurations. In the second part, we study the most favorable configurations in each node by using simulated annealing. This heuristic algorithm allows obtaining approximate solutions of the optimal bias in different types of networks. The results show how the local bias can optimize the exploration of the network in comparison with the unbiased random walk. The methods implemented in this research are general and open the doors to a broad spectrum of tools applicable to different random walk strategies and dynamical processes on networks.

Simple model of epidemic dynamics with memory effects

We introduce a compartment model with memory for the dynamics of epidemic spreading in a constant population of individuals. Each individual is in one of the states S=susceptible, I=infected, or R=recovered (SIR model). In state R an individual is assumed to stay immune within a finite-time interval. In the first part, we introduce a random lifetime or duration of immunity which is drawn from a certain probability density function. Once the time of immunity is elapsed an individual makes an instantaneous transition to the susceptible state. By introducing a random duration of immunity a memory effect is introduced into the process which crucially determines the epidemic dynamics. In the second part, we investigate the influence of the memory effect on the space-time dynamics of the epidemic spreading by implementing this approach into computer simulations and employ a multiple random walker's model. If a susceptible walker meets an infectious one on the same site, then the susceptible one gets infected with a certain probability. The computer experiments allow us to identify relevant parameters for spread or extinction of an epidemic. In both parts, the finite duration of immunity causes persistent oscillations in the number of infected individuals with ongoing epidemic activity preventing the system from relaxation to a steady state solution. Such oscillatory behavior is supported by real-life observations and not captured by the classical standard SIR model.

Activity of vehicles in the bus rapid transit system Metrobús in Mexico City

In this paper, we analyze a massive dataset with registers of the movement of vehicles in the bus rapid transit system Metrobús in Mexico City from February 2020 to April 2021. With these records and a division of the system into 214 geographical regions (segments), we characterize the vehicles' activity through the statistical analysis of speeds in each zone. We use the Kullback-Leibler distance to compare the movement of vehicles in each segment and its evolution. The results for the dynamics in different zones are represented as a network where nodes define segments of the system Metrobús and edges describe similarity in the activity of vehicles. Community detection algorithms in this network allow the identification of patterns considering different levels of similarity in the distribution of speeds providing a framework for unsupervised classification of the movement of vehicles. The methods developed in this research are general and can be implemented to describe the activity of different transportation systems with detailed records of the movement of users or vehicles.

Contact statistics in populations of noninteracting random walkers in two dimensions

The interaction between individuals in biological populations, dilute components of chemical systems, or particles transported by turbulent flows depends critically on their contact statistics. This work clarifies those statistics under the simplifying assumptions that the underlying motions approximate a Brownian random walk and that the particles can be treated as noninteracting. We measure the contact-interval (also called the waiting-time or interarrival-time), contact-count, and contact-duration distributions in populations of individuals undergoing noninteracting continuous-space-time random walks on a periodic two-dimensional plane (a torus) as functions of the population number density, walker radius, and random-walk step size. The contact-interval is exponentially distributed for times longer than the ballistic mean-free-collision time but not for times shorter than that, and the contact duration distribution is strongly peaked at the ballistic-crossing time for head-on collisions when the ballistic-crossing time is short compared to the mean step duration. While successive contacts between individuals are independent, the probability of repeat contact decreases with time after a previous contact. This leads to a negative duration dependence of the waiting-time interval and overdispersion of the contact-count probability density function for all time intervals. The paper demonstrates that for populations of small particles (with a walker radius that is small compared to the mean-separation or random-walk step size), the ballistic mean-free-collision interval, the ballistic-crossing time, and the random-walk-step duration can be used to construct temporal scalings which allow for common waiting-time, contact-count, and contact-duration distributions across different populations. Semi-analytic approximations for both the waiting-time and contact-duration distributions are also presented.

Diffusive transport on networks with stochastic resetting to multiple nodes

We study the diffusive transport of Markovian random walks on arbitrary networks with stochastic resetting to multiple nodes. We deduce analytical expressions for the stationary occupation probability and for the mean and global first passage times. This general approach allows us to characterize the effect of resetting on the capacity of random walk strategies to reach a particular target or to explore the network. Our formalism holds for ergodic random walks and can be implemented from the spectral properties of the random walk without resetting, providing a tool to analyze the efficiency of search strategies with resetting to multiple nodes. We apply the methods developed here to the dynamics with two reset nodes and derive analytical results for normal random walks and Lévy flights on rings. We also explore the effect of resetting to multiple nodes on a comb graph, Lévy flights that visit specific locations in a continuous space, and the Google random walk strategy on regular networks.