Mean First Hitting Time of Searching for Path Through Random Walks on Complex Networks

Abstract

We study the problem of searching for a fixed path ${\epsilon }_0{\epsilon }_1\cdots {\epsilon }_l$ on a network through random walks. We analyze the first hitting time of tracking the path, and obtain exact expression of mean first hitting time $⟨T⟩$. Surprisingly we find that $⟨T⟩$ is divided into two distinct parts: $T_1$ and $T_2$. The first part $T_1=2m{\prod }_{i=1}^{l-1}d({\epsilon }_i)$, is related with the path itself and is proportional to the degree product. The second part $T_2$ is related with the network structure. Based on the analytic results, we propose a natural measure for each path, i.e. $\phi ={\prod }_{i=1}^{l-1}d({\epsilon }_i)$, and call it random walk path measure(RWPM). $\phi$ essentially determines a path's performance in searching and transporting processes. By minimizing $\phi$, we also find RW optimal routing which is a combination of random walk and shortest path routing. RW optimal routing can effectively balance traffic load on nodes and edges across the whole network, and is superior to shortest path routing on any type of complex networks. Numerical simulations confirm our analysis.

6 pages, 4 figures

References in corpus (7)

• Efficient routing on complex networks
• Networks and Cities: An Information Perspective
• Optimal routing on complex networks
• Integrating static and dynamic information for routing traffic
• Statistical properties of sampled networks by random walks
• Diffusive Capture Process on Complex Networks
• Random walks and diameter of finite scale-free networks