Inferring Tree Structure with Hidden Traps from First Passage Times

Abstract

Tracking the movement of tracer particles has long been a strategy for uncovering complex structures. Here, we study discrete-time random walks on finite Cayley trees to infer key parameters such as tree depth and geometric bias toward the root or leaves. By analyzing first passage properties, we show that the first two first-passage-time factorial moments (FPTFMs) uniquely determine the tree structure. However, if the random walker experiences waiting phases -- due to sticky branch walls or presence of traps -- this identification becomes nontrivial. We demonstrate that the generating function of the first passage time (FPT) distribution decomposes into contributions from the waiting time distribution and the random walk without waiting, leading to a nonlinear system of equations relating the factorial moments of the waiting time distribution and the FPTFMs of random walks with and without waiting. For geometrically distributed waiting times, additional moment measurements do not suffice, but unique determination of the structure is achieved by varying initial conditions or fitting the Fourier transform of the FPT distribution to measured data. The latter method remains effective also for power-law waiting time distributions, where higher-order FPTFMs are undefined. These results provide a framework for reconstructing tree-like networks from FPT data, with applications in biological transport and spatial networks.

15 pages, 9 figures

References in corpus (13)

• Epidemic processes in complex networks
• Cayley Trees and Bethe Lattices, a concise analysis for mathematicians and physicists
• Shortest paths and load scaling in scale-free trees
• Trapping in dendrimers and regular hyperbranched polymers
• Dynamics of continuous-time quantum walks in restricted geometries
• Trapping time statistics and efficiency of transport of optical excitations in dendrimers
• Diffusive transport of light in a two-dimensional disordered packing of disks: Analytical approach to transport-mean-free path
• Autocatalytic reaction on low-dimensional substrates
• Enhanced diffusion and anomalous transport of magnetic colloids driven above a two-state flashing potential
• Anomalous biased diffusion in networks
• Path statistics, memory, and coarse-graining of continuous-time random walks on networks
• Trapping in and escape from branched structures of neuronal dendrites
• Unraveling the structure of treelike networks from first-passage times of lazy random walkers