Estimating mean first passage time of biased random walks with short relaxation time on complex networks

Abstract

Biased random walk has been studied extensively over the past decade especially in the transport and communication networks communities. The mean first passage time (MFPT) of a biased random walk is an important performance indicator in those domains. While the fundamental matrix approach gives precise solution to MFPT, the computation is expensive and the solution lacks interpretability. Other approaches based on the Mean Field Theory relate MFPT to the node degree alone. However, nodes with the same degree may have very different local weight distribution, which may result in vastly different MFPT. We derive an approximate bound to the MFPT of biased random walk with short relaxation time on complex network where the biases are controlled by arbitrarily assigned node weights. We show that the MFPT of a node in this general case is closely related to not only its node degree, but also its local weight distribution. The MFPTs obtained from computer simulations also agree with the new theoretical analysis. Our result enables fast estimation of MFPT, which is useful especially to differentiate between nodes that have very different local node weight distribution even though they share the same node degrees.

Figure 1. Nodes with same degree may have very different local connectivity.

The figure shows two examples where a node with degree 3 may be part of a sparsely-connected star network or a densely-connected clique.

Figure 2. Plots of empirical first passage time distribution against theoretical prediction according to the approximate bound given by Ineq.(13) for different networks and weighting factors.

Each row corresponds to a network in the following order: Actor, BA, ER, and arXiv. The columns, from left to right, correspond to , 0, 1 respectively. For most cases, the tail of the first passage time distribution can be predicted fairly accurately except for Figure 2(j), which is due to the high relaxation time as shown in Table 2.

Figure 3. Comparison of MFPTs obtained from simulation against that obtained from using the bound shown in Ineq. (16).

The column on the left compares the empirical MFPT to the results obtained by (i) using the bound in Ineq. (16); (ii) using the result presented in . The column on the right shows the scatter plot and correlation between the empirical results and our proposed theoretical results. The rows correspond to the Actor, arXiv, and BA network respectively. While the result presented by Fronczak et al. gives the general trend of MFPTs with respect to node degree, we find that the MFPTs for a given node degree are distributed across a wide range and cannot be fitted with a function of the node degree alone. The scatter plots show a strong correspondence between the empirical results and our proposed theoretical results. This is further supported by the high Pearson correlation coefficients which are shown on top of the scatter plots.

Figure 4. Relationship between spectral dimension and the weighting factor .

The data used for drawing this figure is tabulated in Table 3. The lines corresponding to BA and ER network appear disconnected as they have for certain values of and cannot be adequately shown in the figure. The spectral dimension generally peaks in the interval [−1, 1] and drops significantly for of greater magnitude. This is especially true for the BA and ER networks (from infinity to a finite value). In the extreme case, by setting , the ‘random walk’ is no longer random as the node with largest degree will always be chosen at every step. Similar reasoning also applies for . Therefore, towards both extremes, we would expect the random walk to become more localized and hence falls into the compact exploration regime.

Figure 5. MFPT of the Actor network when .

Even though the spectral dimension is less than 2, the MFPT is not found to be independent of node degree. Instead, the MFPT exhibits a power-law relationship with respect to the node degree. The disparity arises probably as a result of self-loops, which affects both the RTO probability distribution and the estimated .