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

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

2010-07-12

arxiv.org/abs/1007.1809v1

Physics

Condensed Matter

Disordered Systems and Neural Networks

6 pages, 4 figures

Scientific paper

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 $\langle T \rangle$. Surprisingly we find that $\langle T \rangle$ 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. $\varphi=\prod_{i=1}^{l-1}d(\epsilon_i)$, and call it random walk path measure(RWPM). $\varphi$ essentially determines a path's performance in searching and transporting processes. By minimizing $\varphi$, 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.

Affiliated with

Also associated with

No associations

Rating

Mean First Hitting Time of Searching for Path Through Random Walks on Complex Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Mean First Hitting Time of Searching for Path Through Random Walks on Complex Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mean First Hitting Time of Searching for Path Through Random Walks on Complex Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-695339