Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees

Area of Science:

• Network theory
• Statistical physics
• Graph theory

Background:

• Mean first-passage time (MFPT) determination is a theoretical challenge in network random walks.
• MFPT connects to effective resistance and graph Laplacian eigenvalues.
• Growing treelike networks offer a unique framework for studying these properties.

Purpose of the Study:

• To analytically determine the MFPT between all node pairs in deterministic uniform recursive trees (DURTs).
• To investigate the average trapping time (ATT) for random walks on a specific DURT network with an immobile trap.
• To explore the relationship between trapping behavior and trap location in tree-structured networks.

Main Methods:

• Utilizing the recursive relation of Laplacian spectra derived from DURT construction.
• Analyzing the connections between MFPT, effective resistance, and graph Laplacian eigenvalues.
• Calculating the average of first-passage times (FPT) from all nodes to a designated trap.

Main Results:

• The MFPT for all node pairs in DURTs scales as N ln N for large networks (N nodes).
• The average trapping time (ATT) on a specific DURT network scales linearly with N.
• ATT behavior is influenced by the trap's location, showing parallels with trapping on fractal T-graphs.

Conclusions:

• Exact analytical results for MFPT and ATT were obtained for DURTs.
• The methods presented can be extended to calculate MFPT and ATT in various deterministic media.
• This study provides insights into random walk dynamics on specific growing network structures.