Nonlinear walkers and efficient exploration of congested networks

Random walks are the simplest way to explore or search a graph and have revealed a very useful tool to investigate and characterize the structural properties of complex networks from the real world. For instance, they have been used to identify the modules of a given network, its most central nodes and paths, or to determine the typical times to reach a target. Although various types of random walks whose motion is biased on node properties, such as the degree, have been proposed, which are still amenable to analytical solution, most if not all of them rely on the assumption of linearity and independence of the walkers. In this work we introduce a class of nonlinear stochastic processes describing a system of interacting random walkers moving over networks with finite node capacities. The transition probabilities that rule the motion of the walkers in our model are modulated by nonlinear functions of the available space at the destination node, with a bias parameter that allows to tune the tendency of the walkers to avoid nodes occupied by other walkers. First, we derive the master equation governing the dynamics of the system, and we determine an analytical expression for the occupation probability of the walkers at equilibrium in the most general case and under different level of network congestions. Then we study different types of synthetic and real-world networks, presenting numerical and analytical results for the entropy rate, a proxy for the network exploration capacities of the walkers. We find that, for each level of the nonlinear bias, there is an optimal crowding that maximizes the entropy rate in a given network topology. The analysis suggests that a large fraction of real-world networks are organized in such a way as to favor exploration under congested conditions. Our work provides a general and versatile framework to model nonlinear stochastic processes whose transition probabilities vary in time depending on the current state of the system.