Random walk with priorities in communication-like networks

Abstract

We study a model for a random walk of two classes of particles (A and B). Where both species are present in the same site, the motion of A's takes precedence over that of B's. The model was originally proposed and analyzed in Maragakis et al., Phys. Rev. E 77, 020103 (2008); here we provide additional results. We solve analytically the diffusion coefficients of the two species in lattices for a number of protocols. In networks, we find that the probability of a B particle to be free decreases exponentially with the node degree. In scale-free networks, this leads to localization of the B's at the hubs and arrest of their motion. To remedy this, we investigate several strategies to avoid trapping of the B's: moving an A instead of the hindered B; allowing a trapped B to hop with a small probability; biased walk towards non-hub nodes; and limiting the capacity of nodes. We obtain analytic results for lattices and networks, and discuss the advantages and shortcomings of the possible strategies.

12 pages, 11 figures

References in corpus (13)

• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• Integrating static and dynamic information for routing traffic
• Biased random walks on complex networks: the role of local navigation rules
• Congestion phenomena on complex networks
• Communication Bottlenecks in Scale-Free Networks
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• Jamming transition in traffic flow under the priority queuing protocol
• Exact encounter times for many random walkers on regular and complex networks
• Power laws in zero-range processes on random networks
• Free zero-range processes on networks
• Priority diffusion model in lattices and complex networks
• Random Walks on Complex Networks