Published: Feb. 14, 2019

Dynamics of Nonlinear Random Walks on Complex Networks

Random walks serve as an important tool in the complex networks community due to widespread applications including Google’ PageRank algorithm, community detection, network exploration, and modeling transport. A typical random walk on a network consist of a linear discrete-time dynamical systems, or equivalently, a Markov chain, whose state space describes the probabilities that random walkers occupy different nodes. Typically, transitions between nodes are given by static transition probabilities. However, in applications ranging from transport of resources to human mobility, static transition probabilities are too simplistic to capture realistic behavior. Here we study the dynamics that emerge in nonlinear random walks, where transition probabilities depend on the current system state, thereby changing in time and more accurately capturing complicated behaviors. Specifically, we introduce a tunable bias parameter that, for positive and negative values, respectively, preferentially funnels walks towards nodes that are currently more or less populated. We begin by identifying a weakly nonlinear regime when the bias is sufficiently small in magnitude and prove that, similar to linear random walks, a globally attractive fixed point representing a stationary distribution exists, provided that the network structure is primitive. Next, in the strongly nonlinear regime we find richer dynamics. For negative bias a period-doubling bifurcation occurs, leaving the stationary distribution unstable as the steady-state dynamics oscillate significantly. For positive bias strong multistability emerges, with many stationary distributions emerging. Lastly, we explore structural effects of networks such as directness, which gives rise to even more complicated dynamics, including quasiperiodicity.