Efficient exploration of multiplex networks
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 d...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2016-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/18/4/043035 |
| _version_ | 1827873706133684224 |
|---|---|
| author | Federico Battiston Vincenzo Nicosia Vito Latora |
| author_facet | Federico Battiston Vincenzo Nicosia Vito Latora |
| author_sort | Federico Battiston |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T16:41:03Z |
| format | Article |
| id | doaj.art-fba8b7a997344f70b21895be55d58106 |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:41:03Z |
| publishDate | 2016-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-fba8b7a997344f70b21895be55d581062023-08-08T14:30:56ZengIOP PublishingNew Journal of Physics1367-26302016-01-0118404303510.1088/1367-2630/18/4/043035Efficient exploration of multiplex networksFederico Battiston0Vincenzo Nicosia1Vito Latora2School of Mathematical Sciences, Queen Mary University of London , Mile End Road, E1 4NS, London, UKSchool of Mathematical Sciences, Queen Mary University of London , Mile End Road, E1 4NS, London, UKSchool of Mathematical Sciences, Queen Mary University of London , Mile End Road, E1 4NS, London, UK; Dipartimento di Fisica ed Astronomia, Università di Catania and INFN , I-95123 Catania, ItalyEfficient 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.https://doi.org/10.1088/1367-2630/18/4/043035biased random walksmultiplex networksmulti-layer networksefficient exploration |
| spellingShingle | Federico Battiston Vincenzo Nicosia Vito Latora Efficient exploration of multiplex networks New Journal of Physics biased random walks multiplex networks multi-layer networks efficient exploration |
| title | Efficient exploration of multiplex networks |
| title_full | Efficient exploration of multiplex networks |
| title_fullStr | Efficient exploration of multiplex networks |
| title_full_unstemmed | Efficient exploration of multiplex networks |
| title_short | Efficient exploration of multiplex networks |
| title_sort | efficient exploration of multiplex networks |
| topic | biased random walks multiplex networks multi-layer networks efficient exploration |
| url | https://doi.org/10.1088/1367-2630/18/4/043035 |
| work_keys_str_mv | AT federicobattiston efficientexplorationofmultiplexnetworks AT vincenzonicosia efficientexplorationofmultiplexnetworks AT vitolatora efficientexplorationofmultiplexnetworks |