TY - JOUR
T1 - Nonlinear walkers and efficient exploration of congested networks
AU - Carletti, Timoteo
AU - ASLLANI, Malbor
AU - Fanelli, Duccio
AU - Latora, Vito
N1 - Publisher Copyright:
© 2020 authors. Published by the American Physical Society. Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
PY - 2020/7/2
Y1 - 2020/7/2
N2 - 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.
AB - 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.
KW - dynamics on networks
KW - random walk
KW - entropy
KW - real networks
UR - http://www.scopus.com/inward/record.url?scp=85099605103&partnerID=8YFLogxK
U2 - 10.1103/PhysRevResearch.2.033012
DO - 10.1103/PhysRevResearch.2.033012
M3 - Article
SN - 2643-1564
VL - 2
JO - Physical Review Research
JF - Physical Review Research
IS - 3
M1 - 033012
ER -