Efficient exploration of multiplex networks

Abstract

Efficient techniques to navigate networks with local information are fundamental to sample large-scale online social systems and to retrieve resources in peer-to-peer systems. Biased random walks, i.e. walks whose motion is biased on properties of neighbouring nodes, have been largely exploited to design smart local strategies to explore a network, for instance by constructing maximally mixing trajectories or by allowing an almost uniform sampling of the nodes. Here we introduce and study biased random walks on multiplex networks, graphs where the nodes are related through different types of links organised in distinct and interacting layers, and we provide analytical solutions for their long-time properties, including the stationary occupation probability distribution and the entropy rate. We focus on degree-biased random walks and distinguish between two classes of walks, namely those whose transition probability depends on a number of parameters which is extensive in the number of layers, and those whose motion depends on intrinsically multiplex properties of the neighbouring nodes. We analyse the effect of the structure of the multiplex network on the steady-state behaviour of the walkers, and we find that heterogeneous degree distributions as well as the presence of inter-layer degree correlations and edge overlap determine the extent to which a multiplex can be efficiently explored by a biased walk. Finally we show that, in real-world multiplex transportation networks, the trade-off between efficient navigation and resilience to link failure has resulted into systems whose diffusion properties are qualitatively different from those of appropriately randomised multiplex graphs. This fact suggests that multiplexity is an important ingredient to include in the modelling of real-world systems.

Was 'Biased random walks on multiplex networks'. To appear in New Journal of Physics. 12 pages, 5 figures

References in corpus (16)

• Maps of random walks on complex networks reveal community structure
• Statistical physics of social dynamics
• Synchronization in complex networks
• The structure and dynamics of multilayer networks
• Diffusion dynamics on multiplex networks
• Multirelational Organization of Large-scale Social Networks in an Online World
• Layer aggregation and reducibility of multilayer interconnected networks
• Emergence of network features from multiplexity
• Entropy Rate of Diffusion Processes on Complex Networks
• Maximal-entropy random walks in complex networks with limited information
• Random walks on weighted networks
• Irreducibility of multilayer network dynamics: the case of the voter model
• Emergence of multiplex communities in collaboration networks
• Topologically biased random walk with application for community finding in networks
• Interplay between consensus and coherence in a model of interacting opinions
• Random Walks on Complex Networks

Cited by in corpus (22)

• Human Mobility: Models and Applications
• Random walks on hypergraphs
• Multilayer Networks in a Nutshell
• The new challenges of multiplex networks: measures and models
• Determinants of public cooperation in multiplex networks
• Multilayer Network Science: from Cells to Societies
• Diffusive behavior of multiplex networks
• Enhancing transport properties in interconnected systems without altering their structure
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Diffusion geometry of multiplex and interdependent systems
• Mean encounter times for multiple random walkers on networks
• Reactive random walkers on complex networks
• The Multiplex Efficiency Index: unveiling the Brazilian Air Transportation Multiplex Network -- BATMN
• Algorithmic complexity of multiplex networks
• Optimal exploration of random walks with local bias on networks
• Biased random walkers and extreme events on the edges of complex networks
• Chaos in Nonlinear Random Walks with Non-Monotonic Transition Probabilities
• Maximal dispersion of adaptive random walks
• The Atlas for the Aspiring Network Scientist
• A measure of dissimilarity between diffusive processes on networks
• Non-equilibrium random walks on multiplex networks
• Core-biased random walks in complex networks