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

The determination of mean first-passage time (MFPT) for random walks in networks is a theoretical challenge, and is a topic of considerable recent interest within the physics community. In this paper, according to the known connections between MFPT, effective resistance, and the eigenvalues of graph Laplacian, we first study analytically the MFPT between all node pairs of a class of growing treelike networks, which we term deterministic uniform recursive trees (DURTs), since one of its particular cases is a deterministic version of the famous uniform recursive tree. The interesting quantity is determined exactly through the recursive relation of the Laplacian spectra obtained from the special construction of DURTs. The analytical result shows that the MFPT between all couples of nodes in DURTs varies as $N\text{ln}N$ for large networks with node number $N$. Second, we study trapping on a particular network of DURTs, focusing on a special case with the immobile trap positioned at a node having largest degree. We determine exactly the average trapping time (ATT) that is defined as the average of FPT from all nodes to the trap. In contrast to the scaling of the MFPT, the leading behavior of ATT is a linear function of $N$. Interestingly, we show that the behavior for ATT of the trapping problem is related to the trapping location, which is in comparison with the phenomenon of trapping on fractal T-graph although both networks exhibit tree structure. Finally, we believe that the methods could open the way to exactly calculate the MFPT and ATT in a wide range of deterministic media.

Figure 1

(Color online) The first several iterative processes of a particular network for the case of $m=2$.

Figure 2

(Color online) Mean first-passage time ${⟨F⟩}_g$ as a function of the iteration $g$ on a semilogarithmic scale for different values of parameter $m$. The filled symbols are the numerical results obtained by direct calculation from Eqs. (2, 4), while the empty symbols correspond to the analytical values from Eq. (25), both of which are consistent with each other.

Figure 3

(Color online) Mean first-passage time ${⟨F⟩}_g$ versus the network order $N_g$ on a log-log scale. The filled symbols describe the analytical results shown in Eq. (26). The solid lines represent the corresponding leading scaling given by Eq. (27).

Figure 4

(Color online) The growth process for the first three generations of the particular network corresponding to $m=1$ case.

Figure 5

(Color online) Second construction method of the network for $m=1$ case, which highlights self-similarity. The network after $g+1$ generations, $U_{g+1}$, consists of two replicas of $U_g$ denoted separately by $U_g^{\left(1\right)}$ and $U_g^{\left(2\right)}$, which are connected to each other by adding a link between two hub nodes with one in $U_g^{\left(1\right)}$ and the other in $U_g^{\left(2\right)}$.

Figure 6

Mean trapping time ${⟨T⟩}_g$ as a function of the iteration $g$ on a semilogarithmic scale. The filled symbols are the numerical results obtained by direct calculation via Eq. (2), while the empty symbols correspond to the analytical values provided by Eq. (32). The analytical and numerical values are consistent with each other.