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

Original · EN

We study the problem of searching for a fixed path ε₀ε₁εₗ 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₁ and T₂. The first part T₁ =2m∏ᵢ₌₁ˡ⁻¹d(εᵢ), is related with the path itself and is proportional to the degree product. The second part T₂ is related with the network structure. Based on the analytic results, we propose a natural measure for each path, i.e. φ=∏ᵢ₌₁ˡ⁻¹d(εᵢ), and call it random walk path measure(RWPM). φ essentially determines a path's performance in searching and transporting processes. By minimizing φ, 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.