Efficient exploration of multiplex networks
arXiv:1505.01378 · doi:10.1088/1367-2630/18/4/043035
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.
arXiv commentWas 'Biased random walks on multiplex networks'. To appear in New Journal of Physics. 12 pages, 5 figures
References in corpus (36)
- The structure and function of complex networks
- Epidemic spreading in scale-free networks
- Maps of random walks on complex networks reveal community structure
- Statistical physics of social dynamics
- Synchronization in complex networks
- Multilayer Networks
- The structure and dynamics of multilayer networks
- Diffusion dynamics on multiplex networks
- Multirelational Organization of Large-scale Social Networks in an Online World
- Mathematical Formulation of Multi-Layer Networks
- Structural measures for multiplex networks
- Layer aggregation and reducibility of multilayer interconnected networks
- Random Walks on Multiplex Networks
- Emergence of network features from multiplexity
- Avalanche Collapse of Interdependent Network
- Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
- Contact-based Social Contagion in Multiplex Networks
- Measuring and modelling correlations in multiplex networks
- Entropy Rate of Diffusion Processes on Complex Networks
- Localization of maximal entropy random walk
- Biased random walks on complex networks: the role of local navigation rules
- Exploring complex networks by walking on them
- Network Landscape from a Brownian Particle's Perspective
- Maximal-entropy random walks in complex networks with limited information
- Random walks on weighted networks
- Characteristic times of biased random walks on complex networks
- Irreducibility of multilayer network dynamics: the case of the voter model
- Mean-field diffusive dynamics on weighted networks
- Emergence of multiplex communities in collaboration networks
- Centrality measures and thermodynamic formalism for complex networks
- Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
- Topologically biased random walk with application for community finding in networks
- Characteristic exponents of complex networks
- Interplay between consensus and coherence in a model of interacting opinions
- Non-parametric resampling of random walks for spectral network clustering
- Random Walks on Complex Networks
Cited by in corpus (23)
- Human Mobility: Models and Applications
- Random walks on hypergraphs
- Multilayer Networks in a Nutshell
- Collective phenomena emerging from the interactions between dynamical processes in multiplex networks
- 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
- Biased random walkers and extreme events on the edges of complex networks
- Optimal exploration of random walks with local bias on networks
- Chaos in Nonlinear Random Walks with Non-Monotonic Transition Probabilities
- Maximal dispersion of adaptive random walks
- A measure of dissimilarity between diffusive processes on networks
- The Atlas for the Aspiring Network Scientist
- Non-equilibrium random walks on multiplex networks
- Core-biased random walks in complex networks