Source-linked AI summary
Random Walks on Multiplex Networks
M. De Domenico, A. Sole, S. Gomez, A. Arenas
TL;DR
Multiplex random walks address how agents explore networks with several simultaneous layers. The paper extends established walks, introduces a multiplex-specific physical walk, and derives occupation and coverage expressions. Exploration depends on layer topology, inter-layer strength, and walking strategy, while the disruption data provide only a representative sample.
Problem
The paper examines how random-walk exploration should be modeled when relationships occur across multiple network layers.
Method
The authors extend classical and diffusive random walks to multiplexes, introduce a physical walk, and use supra-Laplacian transition rules and coverage analysis.
Results
Exploration efficiency depends on multiplex topology, inter-layer connection strength, and the adopted walking strategy.
Takeaways & Limitations
The best strategy for covering a multiplex depends on its topology and the weight of inter-layer connections.
Takeaways & Limitations
The London disruption dataset is not complete and is intended only as a fair sample of reasonable, frequent disruptions.
Abstract
from arXiv · showhide
Multiplex networks are receiving increasing interests because they allow to model relationships between networked agents on several layers simultaneously. In this supplementary material for the paper "Navigability of interconnected networks under random failures", we extend well-known random walks to multiplexes and we introduce a new type of walk that can exist only in multiplexes. We derive exact expressions for vertex occupation time and the coverage. Finally, we show how the efficiency in exploring the multiplex critically depends on the underlying topology of layers, the weight of their inter-connections and the strategy adopted to walk.
NAVIGATION STRATEGIES IN INTERCONNECTED NETWORKS
The subsection presents four representative random-walk processes for multiplexes and gives transition rules for constructing their supra-Laplacian matrices.
- Four representative random-walk processes are described to cover a wide variety of real physical processes.
- The corresponding transition rules are provided for building the multiplex supra-Laplacian matrix.
- Other walker types can also be implemented in multiplex networks.
Classical random walkers
Classical random walks extend from monoplex graphs to multiplexes by treating inter-layer connections as additional edges and normalizing movement by total vertex strength.
- Classical random walkers: Classical monoplex random walks move from vertex i to each neighboring vertex with probability 1/k_i.Here, k_i denotes the degree of vertex i.
- Classical random walkers: In multiplexes, inter-layer connections are treated as additional edges available to the walker.
- Classical random walkers: Movement within a layer or switching to a counterpart vertex in another layer is uniformly distributed.
- Classical random walkers: The total strength s_i,α+S_i,α normalizes the transition probabilities for the classical multiplex walker RWC.
Diffusive random walkers
Diffusive random walks make hopping depend on vertex strength, allowing waiting at a vertex and extending the rule to multiplexes through inter-layer connections.
- Diffusive random walkers: The diffusive walker’s hopping rate depends on the vertex from which it moves.
- Diffusive random walkers: A walker waits at vertex i with rate 1−s_i/s_max and jumps with rate s_i/s_max.
- Diffusive random walkers: Unlike the classical walk, this process has vertex-dependent hopping rather than a uniform hopping rate.
- Diffusive random walkers: Its unnormalized Laplacian is the same as that of a classical diffusive process.
- Diffusive random walkers: The multiplex extension uses inter-layer connections when estimating the maximum vertex strength and is called RWD.
Physical random walkers
The physical random walk introduces multiplex-specific dynamics by separating rapid layer switching from vertex movement, allowing both actions in one time step.
- Physical random walkers: The proposed physical walk assumes layer switching is much faster than movement between neighboring vertices.
- Physical random walkers: A walker may switch layers and jump to another vertex during the same time step, with the actions independent.
- Physical random walkers: Unlike earlier walkers, this process permits switching and jumping in the same time unit.
- Physical random walkers: Inter-layer connections are treated as a separate edge type rather than competing with intra-layer edges.
- Physical random walkers: The physical multiplex walker is called RWP and reduces to the classical random walk for monoplex networks.
Maximal entropy random walkers
Maximal entropy random walks choose transitions using global network structure and have multiplex transition rules summarized in Table I. Their dynamics and occupation patterns differ across exploration strategies and inter-layer weights.
- Maximal entropy walkers choose the next vertex by maximizing an entropy-related criterion influenced by the network’s global structure.
- Table I specifies transition probabilities for four multiplex walks, including vertex jumps and layer switches.
- The maximal entropy random walker in a multiplex, RWME, uses transition rules derived from the largest eigenvalue and corresponding eigenvector of a matrix.
- Different inter-layer weights produce visibly different walker dynamics in representative 100-step trajectories.
- Different exploration strategies produce distinct occupation probabilities, with some vertices favored by RWC, RWP, and RWME but uniform occupation for RWD.
- Figures 1 and 2 highlight how navigation strategy influences multiplex exploration.
OCCUPATION PROBABILITY OF RANDOM WALKERS
The occupation probability describes a walker’s long-time distribution over vertices and layers and is obtained from the supra-transition matrix. The resulting distributions distinguish strength-biased classical walks from topology-independent diffusive walks.
- Occupation probability Π_i,α is the long-time probability of finding a walker at vertex i in layer α.
- The occupation vector Π is generally the left eigenvector of the supra-transition matrix associated with eigenvalue one.
- Mean return time gives the expected time for a walker starting at vertex i to return to that same vertex.
- For classical random walks, vertex occupation probability is proportional to suprastrength, combining intra- and inter-layer strengths.
- For diffusive walks, occupation probability is identical for every vertex regardless of multiplex topology.
- The expected monoplex occupation distributions are recovered when the number of layers is L = 1.
DYNAMICAL VS TOPOLOGICAL DESCRIPTORS
Coverage depends jointly on multiplex topology, inter-layer strength, and navigation strategy. The second smallest supra-Laplacian eigenvalue tracks coverage dynamics, while strong inter-layer coupling can delay exploration.
- Topology: Different multiplex topologies visit vertices on different time scales, relative to an ER monoplex baseline.This topology effect persists for multiplexes with 2000 nodes, showing it is not merely a finite-size effect.
- Navigation strategy: The best coverage strategy depends on layer topology and inter-layer weight, and changing the covered fraction alters results quantitatively but not qualitatively.Figure 5 measures the inverse time to cover 50% of a BA+ER multiplex as a function of DX.
- Diffusion regimes: RWME on BA+BA produces enhanced diffusion in the multiplex, whereas the other illustrated topology–strategy combinations are infra-diffusive.For RWC on BA+BA, multiplex and single-layer diffusion are similar; the enhanced case has a smaller multiplex coverage time than either layer separately.
- Dynamical vs topological descriptors: The inverse 50% coverage time and λ2 show similar dependence on DX across BA+BA, BA+ER, and ER+ER multiplexes, except at the smallest DX values.The comparison uses four random walks and treats 1/τC and λ2 as dynamical and topological descriptors.
- Inter-layer strength: Increasing DX increases the time required to cover a given multiplex fraction because walkers spend more time switching layers than jumping between vertices.The stated mechanism applies when DX is much larger than the average vertex strength.
- Spectral limits: For vanishing inter-layer connections, λ2 is proportional to DX and coverage becomes independent of DX, reducing to single-layer coverage.This limit corresponds to a multiplex with vanishing inter-layer connections.
DYNAMICAL VS TOPOLOGICAL RESILIENCE
The paper distinguishes navigability resilience, measured through coverage after failures, from structural resilience, measured through giant-component survival. In London’s public transport multiplex, navigability resilience is lower than topological resilience, while inter-layer connectivity enhances resilience relative to monoplexes.
- Dynamical resilience: Navigability resilience measures coverage after random failures, normalized against coverage without failures.The framework defines r(φ) as the average failed-network coverage divided by baseline coverage.
- Multiplex effect: Inter-layer connectivity enhances the system’s resilience relative to monoplex networks.
- Topological resilience: Topological resilience is the average fraction of vertices surviving in the giant connected component after random failures.
- Comparison: Navigability resilience is inherently smaller than the multiplex’s topological resilience.
EMPIRICAL DATA OF REAL DISRUPTED SERVICES IN LONDON
Because official and historical disruption records were incomplete, the study assembled a Twitter-based sample and used it to simulate representative partial and whole-line failures. The resulting data-driven resilience estimates closely matched theoretical expectations.
- Data sources: Official TfL data covered Tube status but omitted Overground and DLR disruptions and lacked historical disruption records.
- Data collection: The study collected tweets containing “no service” from line-specific accounts between 11 February 2012 and 26 March 2014.
- Data processing: More than 3000 tweets were collected, with conservative heuristics classifying 64% into 357 unique disrupted station pairs.
- Scope: The disruption dataset was intended as a fair sample of reasonable and frequent disruptions, not complete information about real London disruptions.
- Disruption scenarios: The study included manually extracted whole-line disruptions and tested all 11 possible full-line disruption scenarios.
- Validation: Data-driven simulations showed remarkable agreement with theoretical resilience calculations for representative partial and whole-line disruptions.