Unraveling the structure of treelike networks from first-passage times of lazy random walkers

Abstract

We study the problem of random search in finite networks with a tree topology, where it is expected that the distribution of the first-passage time F(t) decays exponentially. We show that the slope of the exponential tail is independent of the initial conditions of entering the tree in general, and scales exponentially or as a power law with the extent of the tree L, depending on the tendency p to jump toward the target node. It is unfeasible to uniquely determine L and p from measuring the tail slope or the mean first-passage time (MFPT) of an ordinary diffusion along the tree. To unravel the structure, we consider lazy random walkers that take steps with probability m when jumping on the nodes and return with probability q from the leaves. By deriving an exact analytical expression for the MFPT of the intermittent random walk, we verify that the structural information of the tree can be uniquely extracted by measuring the MFPT for two randomly chosen types of tracer particles with distinct experimental parameters m and q. We also address the applicability of our approach in the presence of disorder in the structure of the tree or statistical uncertainty in the experimental parameters.

arXiv comment9 pages, 8 figures

References in corpus (20)

• The architecture of complex weighted networks
• Weighted Evolving Networks
• Shortest paths and load scaling in scale-free trees
• Anomalous Diffusion with Absorbing Boundary
• Trapping in dendrimers and regular hyperbranched polymers
• Random walk on Bethe lattice and hyperbolic geometry
• Dynamics of continuous-time quantum walks in restricted geometries
• Anomalous Diffusion of Self-Propelled Particles in Directed Random Environments
• A Microscopic Model for Packet Transport in the Internet
• Run-and-pause dynamics of cytoskeletal motor proteins
• Trapping time statistics and efficiency of transport of optical excitations in dendrimers
• Persistent-random-walk approach to anomalous transport of self-propelled particles
• Biased diffusion in a one-dimensional adsorbed monolayer
• Diffusive transport of light in a two-dimensional disordered packing of disks: Analytical approach to transport-mean-free path
• Enhanced diffusion and anomalous transport of magnetic colloids driven above a two-state flashing potential
• Autocatalytic reaction on low-dimensional substrates
• Statistics of Weighted Networks
• Anomalous biased diffusion in networks
• Trapping in and escape from branched structures of neuronal dendrites
• Transmission of packets on a hierarchical network: Statistics and explosive percolation

Cited by in corpus (7)

• Persistence-Speed Coupling Enhances the Search Efficiency of Migrating Immune Cells
• Transient anomalous diffusion in run-and-tumble dynamics
• Orientational Memory of Active Particles in Multistate Non-Markovian Processes
• Kinematics of Persistent Random Walkers with Two Distinct Modes of Motion
• Vulnerability of Transport through Evolving Spatial Networks
• Tracking the Morphological Evolution of Neuronal Dendrites by First-Passage Analysis
• Inferring Tree Structure with Hidden Traps from First Passage Times