University of Limerick Institutional Repository

Nonlinear walkers and efficient exploration of congested networks

DSpace Repository

Show simple item record Carletti, Timoteo Asllani, Malbor Fanelli, Duccio Latora, Vito 2021-01-20T09:27:33Z 2021-01-20T09:27:33Z 2020
dc.description peer-reviewed en_US
dc.description.abstract 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. en_US
dc.language.iso eng en_US
dc.publisher American Physical Society en_US
dc.relation.ispartofseries Physical Review Research;2, 033012
dc.subject Random walks en_US
dc.subject complex networks en_US
dc.title Nonlinear walkers and efficient exploration of congested networks en_US
dc.type info:eu-repo/semantics/article en_US
dc.type.supercollection all_ul_research en_US
dc.type.supercollection ul_published_reviewed en_US
dc.identifier.doi 10.1103/PhysRevResearch.2.033012
dc.rights.accessrights info:eu-repo/semantics/openAccess en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ULIR


My Account