Please use this identifier to cite or link to this item:

Random walk in networks : first passage time and speed analysis

Authors Lau, Hon Wai
Issue Date 2009
Summary Spreading of epidemic, stochastic resonance, chemical reaction and neuron firing dynamics can be described by the random walk first passage process. These phenomena are characterized by first encountering events with target points. Other than the widely studied mean first passage time (MFPT), we study the mean first passage speed (MFPS) which is the mean of distance traveled divided by first passage time. By analyzing random walk in the ring topology, we have found analytically that the MFPS <s> decrease as <s> ~1/θ near the starting point. A surprising result suggests that a minimum of MFPS exists at the universal location θ = 0.811π which is not the opposition of the starting point. The same phenomenon of MFPS also exists in 2D and 3D torus. The second part studies the MFPT in complex network. We show that the tail of first passage time distribution F(vd, t) ~ exp [ - βdt] depends only on the destination node vd, and we also find the explicit method to compute the decay rate βd. For networks with short relaxation time and source node far from destination node, the MFPT is argued to be <T> ≈1 / βd and inversely proportional to the destination node degree. Since Erd˝os-Rényi and Barabási-Albert network have short relaxation time, the results apply and are confirmed numerically. The results of real world networks suggested that the MFPT computed is a lower bound of the actual MFPT. Furthermore, we analyze random walk with multiple non-interacting exclusive walkers such that each node can only have zero or one walker. The equilibrium occupation is given by the Fermi-Dirac distribution. By performing similar analysis of single random walker, the result suggests that MFPT is related to occupation number and degree of node.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2009
Language English
Format Thesis
Files in this item:
File Description Size Format
th_redirect.html 339 B HTML