Determining mean first-passage time on a class of treelike regular fractals

Lin Yuan, Bin Wu, Zhongzhi ZhangPhysical 2010 · DOI · arXiv

Abstract

Relatively general techniques for computing mean first-passage time (MFPT) of random walks on networks with a specific property are very useful since a universal method for calculating MFPT on general graphs is not available because of their complexity and diversity. In this paper, we present techniques for explicitly determining the partial mean first-passage time (PMFPT) and the entire mean first-passage time (EMFPT) on regular treelike fractals. The proposed fractals include the T fractal and the Peano basin fractal as special cases. We provide a formula for MFPT between two directly connected nodes in general trees and derive an exact expression for PMFPT to the central node. Moreover, we give a technique for calculating EMFPT based on the relationship between characteristic polynomials of the fractals at different generations, avoiding the computation of eigenvalues.

Introduction

In the study of dynamical processes, the Mean First-Passage Time (MFPT) is a crucial quantity. It represents the expected number of steps a random walker takes to travel from a source node to a target node. This metric is used to model everything from chemical reactions and nutrient transport in cells to the spread of information in social networks.

While calculating MFPT is straightforward for simple grids, it becomes incredibly complex for general graphs. Fractals—structures that look the same at different scales—are excellent models for complex real-world systems, but most existing methods for calculating their MFPT are "one-offs" designed for a single specific structure. This research develops a generalized method to calculate MFPT for a broad class of treelike fractals.

Methodology

The authors define a family of fractals controlled by a parameter $m$. Starting with a single edge ($g=0$), each iteration replaces an edge with a more complex structure.

Construction rule for the fractal family based on parameter $m$.

As shown in Figure 1, the parameter $m$ determines how many new nodes are attached to the middle of the newly created two-link path. This family includes the well-known T-fractal ($m=1$) and the Peano basin fractal ($m=2$) as special cases. The structure grows iteratively through generations $g$.

Evolution of the fractal structure through generations $g=0$ to $g=3$.

To solve for MFPT, two distinct strategies were employed:

  1. Adjacent Node Formula: For Partial MFPT (PMFPT)—the average time to reach a fixed central trap—they used a universal property of trees: the MFPT between two adjacent nodes $u$ and $v$ is simply $2C_{u<v} - 1$, where $C_{u<v}$ is the number of nodes in the subtree "behind" the walker.
  2. Polynomial Recursion: For Entire MFPT (EMFPT)—the average time between all possible pairs of nodes—the standard approach involves finding the eigenvalues of the Laplacian matrix. Instead, the authors derived recursion relations between the characteristic polynomials of the fractal at different generations ($g$ and $g+1$). This allowed them to find the sum of the reciprocal of the eigenvalues without heavy matrix diagonalization.

Key Insights and Results

  • The Power of Subtrees: In a tree structure, the "cost" of moving between neighbors is purely a function of the local geometry (the size of the branch you are leaving). This simplifies the global trapping problem into a counting exercise of nodes in subtrees.
  • Avoiding Eigenvalues: By finding how the coefficients of characteristic polynomials evolve through iterations, the researchers bypassed the need for heavy matrix diagonalization to calculate EMFPT.
  • Efficiency vs. Complexity: The parameter $m$ acts as a "tuning knob" for transport efficiency. As $m$ increases, the fractal becomes more "dense" around its internal nodes, making the trapping process more efficient.

The paper provides exact formulas for both PMFPT and EMFPT. Both measures of navigation time grow as a power-law function of the number of nodes ($N_g$). Specifically, they scale as: $$\langle F \rangle_g \sim (N_g)^{1 + \frac{\ln 2}{\ln(m+2)}}$$

The scaling exponent $\theta(m) = 1 + \frac{\ln 2}{\ln(m+2)}$ is a decreasing function of $m$. This means that while navigation time always grows faster than the number of nodes (superlinearly), increasing the branching factor $m$ makes the growth relatively slower and the "trapping" more efficient.

Conclusion

These techniques are strictly applicable to treelike structures (graphs without loops), where the single path between nodes allows for subtree-counting methods. The polynomial recursion method is quite general and could potentially be adapted for more complex fractals that contain loops, though the recursion relations would be significantly more complex. This framework provides a powerful tool for understanding transport efficiency in self-similar networked systems.

Summary updated

Abstract

Relatively general techniques for computing mean first-passage time (MFPT) of random walks on networks with a specific property are very useful since a universal method for calculating MFPT on general graphs is not available because of their complexity and diversity. In this paper, we present techniques for explicitly determining the partial mean first-passage time (PMFPT), i.e., the average of MFPTs to a given target averaged over all possible starting positions, and the entire mean first-passage time (EMFPT), which is the average of MFPTs over all pairs of nodes on regular treelike fractals. We describe the processes with a family of regular fractals with treelike structure. The proposed fractals include the T fractal and the Peano basin fractal as their special cases. We provide a formula for MFPT between two directly connected nodes in general trees on the basis of which we derive an exact expression for PMFPT to the central node in the fractals. Moreover, we give a technique for calculating EMFPT, which is based on the relationship between characteristic polynomials of the fractals at different generations and avoids the computation of eigenvalues of the characteristic polynomials. Making use of the proposed methods, we obtain analytically the closed-form solutions to PMFPT and EMFPT on the fractals and show how they scale with the number of nodes. In addition, to exhibit the generality of our methods, we also apply them to the Vicsek fractals and the iterative scale-free fractal tree and recover the results previously obtained.
BibTeX
@inproceedings{yuan2010determining,
  author = {Lin Yuan and Bin Wu and Zhongzhi Zhang},
  title = {{Determining mean first-passage time on a class of treelike regular fractals}},
  booktitle = {Physical},
  year = {2010},
  doi = {10.1103/physreve.82.031140},
}
Figure