# Comparison of Multiple Random Walks Strategies for Searching Networks

Authors: Zhongtuan Zheng; Hanxing Wang; Shengguo Gao; Guoqiang Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We investigate diverse random-walk strategies for searching networks, especially multiple random walks (MRW). We use random walks on weighted networks to establish various models of single random walks and take the order statistics approach to study corresponding MRW, which can be a general framework for understanding random walks on networks. Multiple preferential random walks (MPRW) and multiple simple random walks (MSRW) are two special types of MRW. As search strategies, MPRW prefers high-degree nodes while MSRW searches for low-degree nodes more efficiently. We analyze the first passage time (FPT) of wandering walkers of MRW and give the corresponding formulas of probability distributions and moments, and the mean first passage time (MFPT) is included. We show the convergence of the MFPT of the first arriving walker and find the MFPT of the last arriving walker closely related with the mean cover time. Simulations confirm analytical predictions and deepen discussions. We use a small random network to test the FPT properties from different aspects. We also explore some practical search-related issues by MRW, such as detecting unknown shortest paths and avoiding poor routings on networks. Our results are of practical significance for realizing optimal routing and performing efficient search on complex networks.


---

## Body

## 1. Introduction

A random walk on a network [1] is precisely what its name says: a walk X0X1⋯ operated in a certain random fashion. Starting a random walk at X0, its next node, X1, is selected at random from among the neighbours of X0; then X2 is a random neighbour of X1, and so on. Namely, the stochastic sequence of nodes selected this way is a random walk on the network, which mainly depends on the network structure.Random walks on complex networks are a fundamental dynamic process, which can be used to model various dynamic stochastic systems in physical, biological, or social contexts such as diffusive motion [2], traffic flow [3], synchronization [4], animals movement [5], and epidemic spread [6]. It could also be a mechanism of transport and search in real-world networks [7–9], when no global information of the underlying networks is available. For instance, in some networks, such as wireless sensor networks [10], ad hoc networks [11], and peer-to-peer networks [12], data packets traverse the networks in a random-walk fashion. It has been demonstrated that the structural properties of networks, such as the large connectivity heterogeneity and the short average distance, play an essential role in determining the scaling features of the random-walk search for complex networks [13]. Recent studies show that random walks on complex networks can also reveal a variety of characteristics of the network [14].First passage time (FPT) and cover time (CT) are two important characteristics of random walks on complex networks, which heavily rely on the underlying network topology [15–17]. FPT, denoted by Tsh, is the number of steps the random walker takes to arrive at the destination node h for the first time after starting from the source node s. Correspondingly, the mean FPT (MFPT), that is, the expectation of Tsh is denoted by 〈Tsh〉 or ETsh. For a random walk on a network, the vertex CT is the number of steps the random walker takes to reach every node, and the edge CT is the number of steps the walker takes to traverse every edge. Let ECVs be the expectation of vertex CT (or the mean vertex CT), and let ECEs be the expectation of edge CT (or the mean edge CT) if the walk starts at node s. FPT and CT of a single walker or multiple walkers in complex networks have been studied in a number of articles [16–22]. These results are frequently based on the spectral properties of the adjacency matrix of the graph and of the transition matrix of the random walk [13, 21, 22].However, thus far, the comparison of random-walk strategies for searching complex networks remains less understood, especially MRW strategies. Furthermore, a uniform analysis of various MRW strategies is still lacking. In this paper, based on random walks on weighted networks, we establish various models of single random walks and then construct corresponding MRW. By means of the order statistics, we mainly investigate the behaviors of the first and last arriving walkers when all the walkers start from the same source simultaneously and head to the same destination randomly, that is, MRW on networks. We focus on the FPT and the MFPT of MRW, which are closely related to the distance between a selected pair of nodes and the CT of corresponding single random walks. Considering the MRW as the search strategy, the FPT of the first arriving walker, to a certain extent, characterizes the search efficiency while that of the last arriving walker portrays network searchability [7]. In future, the MRW search strategy could be used to fast detect the unknown shortest path and avoid the worst routing between a pair of nodes.


## 2. Single Random Walks on Networks

First, we take a look at single random walks on an arbitrary finite network (or graph)G=(V,E). The network consists of nodes (or vertexes, sites) i=1,2,…,N and links (or edges) connecting them. We assume that the network is connected; that is, there is a path between each pair of nodes; otherwise, we simply consider each component separately. To implement a random walk, each node needs to calculate the transition probability from the node to each of its adjacent ones. In this paper, we mainly perform preferential random walks (PRW) on networks by the following rule. The rule is that a walker, wandering on the network, randomly selects a neighboring node as its next dwelling point according to the degrees of neighboring nodes. So the probability of jumping to any neighboring node is pij=P(Xt+1=j∣Xt=i)=dj/∑j∈τ(i)‍dj, where dj denotes the degree, the number of connected neighbors, of a node j, and τ(i) denotes all the connected neighbors of node i. Transforming the pij into djdi/∑j∈τ(i)‍djdi, we have defined a Markov chain on the network with a transition matrix as follows:
(1)pij={djdi∑j∈τ(i)djdi,(i,j)∈E,0,(i,j)∉E.We make comparative studies with simple random walks (SRW), of which the transition matrix is(2)pij={1di,(i,j)∈E,0,(i,j)∉E.In fact, as (1) and (2) show, if SRW and PRW being search strategies on networks, PRW prefers the high-degree node, while SRW searches for the relatively low-degree node more efficiently.More generally, for the networkG=(V,E), we assign a positive weight 0<cij=cji<∞ to link (i,j); otherwise, if the link (i,j) is absent, we attach weight cij=cji=0. Writing c for the function ij↦cij, we have obtained the weighted network (G,c). Define a random walk on the weighted network as a sequence of random variables Xt:t=0,1,2,…, each taking values in the set V of nodes. And the sequence Xt:t=0,1,2,… is such that if Xt=i, namely, at time t, the walk is at node i; then with the transition probability pij=cij/∑j‍cij the walk is at node j at the next time t+1; that is to say, the walk randomly selects a neighboring node as its next dwelling point according to link weights. Such a walk is named a single random walk on the weighted network or a single weighted random walk. Clearly, the sequence Xt:t=0,1,2,… is a Markov chain with the finite space V, whose transition matrix P satisfies [15]
(3)pij=P(Xt+1=j∣Xt=i)={cijci,(i,j)∈E,0,(i,j)∉E,
where ci=∑j‍cij.Thereby, we can use a uniform method to study PRW and SRW on networks. If we attach weightcij=djdi to each link (i,j), then the random walk on the weighted network is a PRW. Whereas, if we assign weight cij=1 to each link (i,j), then the one is an SRW that we always say. Both of them are irreducible and reversible Markov chains.Random walks mentioned below include SRW and PRW unless particularly noted. Now we randomly select a pair of nodes on the network, one node as sources, the other as destination h. Let Tsh be the number of steps the walker takes to arrive at the destination h for the first time after starting from the source s, namely, FPT. Tsh is a nonnegative integer-valued random variable. The probability distribution is denoted by
(4)p(t)=P(Tsh=t),t=0,1,2,…,dsh-1,dsh,dsh+1,…,m,m+1,…,
where dsh is being the distance (or the shortest path length) between the source and the destination; here we assume s≠h.In this paper, we investigate the FPT and MFPT for single random walks by analysis of the transition matrix. We define a matrixM(h) [22] associated with the transition matrix P. M(h) is got from P by setting hth column of P to zero; that is,
(5)M(h)=(P1,…,Ph-1,0,Ph+1,…,PN).
Thus,
(6)P(Tsh>t)=∑i=1N‍(M(h)t)si,t=0,1,2,…,(7)P(Tsh⩽t)=1-∑i=1N‍(M(h)t)si,t=0,1,2,…,(8)P(Tsh=t)=∑i=1N‍(M(h)t-1-M(h)t)si,t=1,2,…,(9)ETsh=∑t=0∞‍P(Tsh>t)=∑i=1N‍(1I-M(h))si,where1I-M(h)≜(I-M(h))-1.By the way, in our another paper unpublished, by using the stopping time technique, we derive an exact formula of the MFPT, denoted byETij or 〈Tij〉, for the PRW on networks. Considering the PRW on the finite network, the MFPT of node j from node i is
(10)〈Tij〉={1πj=∑j∑i∈τ(j)(didj)‍∑i∈τ(j)(didj),i=j,1πj(Rjj-Rij),i≠j,
where
(11)Rij=∑t=0∞‍(pij(t)-πj);
thus, the average MFPT over all node pairs ij  (i≠j) is
(12)〈〈Tij〉〉=∑i‍∑j‍πiπj〈Tij〉=∑j‍πj〈Tij〉=∑j‍Rjj.


## 3. Multiple Random Walks on Networks

### 3.1. Formation of Multiple Random Walks

Based on the above discussion, we are now able to further considerz parallel, independent single weighted random walks that start from the same node, which form the multiple weighted random walks with z walkers, abbreviated as MRW. We mainly analyze the FPT problem of MPRW and MSRW, which are two special types of multiple weighted random walks and, respectively, correspond to PRW and SRW. Suppose there are z walkers wandering independently from the same source simultaneously to the same destination on the network. FPTs of walkers are, respectively, denoted by
(13)Tsh1,Tsh2⋯Tshz.
They are independent random variables with the same distribution of Tsh. Let Tsh(i) be the ith order statistics [23] given by
(14)Tsh(1),Tsh(2)⋯Tsh(z),
where they are arranged from Tshi’s independent observations from the discrete distribution of Tsh. That is to say, Tsh(1), Tsh(z), and Tsh(i) denote FPTs of the first, last, and ith arriving walkers, respectively.


### 3.2. FPT of Multiple Random Walks

In this subsection, we explore the FPT of the first and last arriving walkers and present the corresponding equations of the probability distribution, the joint distribution, and moments as well. Further, we study the relationship between the MFPT of the first arriving walker and the distance between the selected two nodes, as well as the relationship between the MFPT of the last arriving walker and the mean CT of corresponding single random walks. Taking advantage of the order statistics technique and using (6)–(9), we can easily get the following formulas, of which the detailed proofs are omitted. Note that the results in this subsection generally hold for multiple weighted random walks, including MPRW and MSRW. We would like to stress that some time ago similar calculations were only done for the FPT of the first arriving walker for MSRW on networks. Results presented in our paper encompass the results of [24] as a special case.


#### 3.2.1. Probability Distributions ofTsh(1) and Tsh(z)

P
(
t
)
=
P
(
T
s
h
⩽
t
)
=
∑
α
=
0
t
P
(
T
s
h
=
α
)
=
∑
α
=
0
t
p
(
α
), where p(t) and P(Tsh⩽t) are given by (7) and (8), respectively,
(15)p*(t1)=P(Tsh(1)=t1)=(1-P(t1-1))z-(1-P(t1))z=(∑i=1N‍(M(h)t1-1)si)z-(∑i=1N‍(M(h)t1)si)z,hhhhhhhhhhhhhhhhhhhhhhhhhhhht1=1,2,…,(16)p*(tz)=P(Tsh(z)=tz)=(P(tz))z-(P(tz-1))z=(1-∑i=1N‍(M(h)tz)si)z-(1-∑i=1N‍(M(h)tz-1)si)z,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhtz=1,2,….


#### 3.2.2. Joint Distributions of(Tsh(1),Tsh(z)) and Distributions of Rz=Tsh(z)-Tsh(1)

(1) Joint distributions of
(
T
s
h
(
1
)
,
T
s
h
(
z
)
)
.When Tsh(1)=Tsh(z),
(17)P(Tsh(1)=Tsh(z)=t)=(p(t))z=(∑i=1N‍(M(h)t-1-M(h)t)si)z,hhhhhhhhhhhhht=0,1,2,….WhenTsh(1)<Tsh(z),
(18)P(Tsh(1)=t1,Tsh(z)=tz)=(P(tz)-P(t1-1))z-(P(tz-1)-P(t1-1))z-(P(tz)-P(t1))z+(P(tz-1)-P(t1))z=((1-∑i=1N‍(M(h)tz)si)-(1-∑i=1N‍(M(h)t1-1)si))z-((1-∑i=1N‍(M(h)tz-1)si)hhh-(1-∑i=1N‍(M(h)t1-1)si))z-((1-∑i=1N‍(M(h)tz)si)-(1-∑i=1N‍(M(h)t1)si))z+((1-∑i=1N‍(M(h)tz-1)si)hhh-(1-∑i=1N‍(M(h)t1)si))z,
where t1,t2=1,2,….(2) Distributions of
R
z
=
T
s
h
(
z
)
-
T
s
h
(
1
)
.When Tsh(1)=Tsh(z),
(19)P(Rz=0)=∑t=0∞‍(p(t))z=∑t=0∞‍(∑i=1N‍(M(h)t-1-M(h)t)si)z.WhenTsh(1)<Tsh(z),
(20)P(Rz=rz)=∑t1=1∞‍P(Tsh(1)=t1,Tsh(z)=rz+t1)rz>0=∑t1=1∞‍[((1-∑i=1N‍(M(h)rz+t1)si)hhhhhh-(1-∑i=1N‍(M(h)t1-1)si))zhhhh-((1-∑i=1N‍(M(h)rz+t1-1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1-1)si))zhhhh-((1-∑i=1N‍(M(h)rz+t1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1)si))zhhhh+((1-∑i=1N‍(M(h)rz+t1-1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1)si))z].


#### 3.2.3. Moment Analysis of FPT

Consider the following:(21)ETsh(1)=∑t1=0∞‍(1-P(t1))z=∑t1=0∞‍(∑i=1N‍(M(h)t1)si)z,(22)E(Tsh(1))2=2∑t1=0∞‍t1(1-P(t1))z+ETsh(1)=2∑t1=0∞‍t1(∑i=1N‍(M(h)t1)si)z+ETsh(1),V(Tsh(1))=E(Tsh(1))2-(ETsh(1))2=2∑t1=0∞‍t1(∑i=1N‍(M(h)t1)si)z+ETsh(1)(1-ETsh(1)),(23)ETsh(z)=∑tz=0∞‍[1-P(tz)z]=∑tz=0∞‍(1-[1-∑i=1N‍(M(h)tz)si]z),(24)E(Tsh(z))2=2∑tz=0∞‍tz[1-P(tz)z]+ETsh(z)=2∑tz=0∞‍tz(1-[1-∑i=1N‍(M(h)tz)si]z)+ETsh(z),V(Tsh(z))=2∑tz=0∞‍tz(1-[1-∑i=1N‍(M(h)tz)si]z)+ETsh(z)(1-ETsh(z)),(25)ERz=∑t=0∞‍(1-P(t)z-[1-P(t)]z)=∑t=0∞‍(1-[1-∑i=1N‍(M(h)t)si]z-[∑i=1N‍(M(h)t)si]z),(26)V(Rz)=2∑tz=0∞‍∑t1=0tz‍(1-P(tz)z-[1-P(t1)]zhhhhhhh+[P(tz)-P(t1)]z)-ERz(1+ERz).We can investigate general cases ofTsh(i) and (Tsh(i),Tsh(j)), respectively, in a similar way. Distributions, joint distributions, moments, and more characteristics of these FPTs could be easily got, the range Tsh(j)-Tsh(i) as well. The discrete-time results obtained here can also be compared with those for multiple continuous-time random walks. We leave these problems to our future work.


### 3.3. MFPT of the First Arriving Walker

Since there is no path with a length shorter thandsh and at least one path with a length equal to dsh from the source to the destination, the FPT of single random walk on networks clearly satisfies P(Tsh<dsh)=0, P(Tsh=dsh)>0, Then, combining with (15) and (21), it is not difficult to obtain the following results:
(27)P(Tsh(1)=dsh)⟶1(z⟶∞),(28)ETsh(1)⟶dsh(z⟶∞),(29)VTsh(1)⟶0(z⟶∞).That is to say, the first arriving walker of MRW will take the shortest path or near shortest path with high probability if the walker number is large enough.


### 3.4. MFPT of the Last Arriving Walker

How long does one have to walk before he sees all nodes or traverse all edges in a network? The answer to this question is the vertex CT and edge CT. In the following, we mainly consider the coverage problem of single random walks on a simple network by using numerical simulation. For a simple random walk on a simple general network, the better upper bound of the mean vertex cover time isO(|V||E|) [25], which is well verified by the simulations.An interesting problem is what the number of walkersz will arrive at when the MFPT of the last arriving walker has a consensus with or exceeds the mean cover time of corresponding single random walks. To address this problem, the paper that only gives the simulation analysis. We find the MFPT of the last arriving walker will be significantly more than the mean cover time ECVs and ECEs, when walker number z is network size N of several orders of magnitude, that is, z=N×10k.


## 3.1. Formation of Multiple Random Walks

Based on the above discussion, we are now able to further considerz parallel, independent single weighted random walks that start from the same node, which form the multiple weighted random walks with z walkers, abbreviated as MRW. We mainly analyze the FPT problem of MPRW and MSRW, which are two special types of multiple weighted random walks and, respectively, correspond to PRW and SRW. Suppose there are z walkers wandering independently from the same source simultaneously to the same destination on the network. FPTs of walkers are, respectively, denoted by
(13)Tsh1,Tsh2⋯Tshz.
They are independent random variables with the same distribution of Tsh. Let Tsh(i) be the ith order statistics [23] given by
(14)Tsh(1),Tsh(2)⋯Tsh(z),
where they are arranged from Tshi’s independent observations from the discrete distribution of Tsh. That is to say, Tsh(1), Tsh(z), and Tsh(i) denote FPTs of the first, last, and ith arriving walkers, respectively.


## 3.2. FPT of Multiple Random Walks

In this subsection, we explore the FPT of the first and last arriving walkers and present the corresponding equations of the probability distribution, the joint distribution, and moments as well. Further, we study the relationship between the MFPT of the first arriving walker and the distance between the selected two nodes, as well as the relationship between the MFPT of the last arriving walker and the mean CT of corresponding single random walks. Taking advantage of the order statistics technique and using (6)–(9), we can easily get the following formulas, of which the detailed proofs are omitted. Note that the results in this subsection generally hold for multiple weighted random walks, including MPRW and MSRW. We would like to stress that some time ago similar calculations were only done for the FPT of the first arriving walker for MSRW on networks. Results presented in our paper encompass the results of [24] as a special case.


### 3.2.1. Probability Distributions ofTsh(1) and Tsh(z)

P
(
t
)
=
P
(
T
s
h
⩽
t
)
=
∑
α
=
0
t
P
(
T
s
h
=
α
)
=
∑
α
=
0
t
p
(
α
), where p(t) and P(Tsh⩽t) are given by (7) and (8), respectively,
(15)p*(t1)=P(Tsh(1)=t1)=(1-P(t1-1))z-(1-P(t1))z=(∑i=1N‍(M(h)t1-1)si)z-(∑i=1N‍(M(h)t1)si)z,hhhhhhhhhhhhhhhhhhhhhhhhhhhht1=1,2,…,(16)p*(tz)=P(Tsh(z)=tz)=(P(tz))z-(P(tz-1))z=(1-∑i=1N‍(M(h)tz)si)z-(1-∑i=1N‍(M(h)tz-1)si)z,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhtz=1,2,….


### 3.2.2. Joint Distributions of(Tsh(1),Tsh(z)) and Distributions of Rz=Tsh(z)-Tsh(1)

(1) Joint distributions of
(
T
s
h
(
1
)
,
T
s
h
(
z
)
)
.When Tsh(1)=Tsh(z),
(17)P(Tsh(1)=Tsh(z)=t)=(p(t))z=(∑i=1N‍(M(h)t-1-M(h)t)si)z,hhhhhhhhhhhhht=0,1,2,….WhenTsh(1)<Tsh(z),
(18)P(Tsh(1)=t1,Tsh(z)=tz)=(P(tz)-P(t1-1))z-(P(tz-1)-P(t1-1))z-(P(tz)-P(t1))z+(P(tz-1)-P(t1))z=((1-∑i=1N‍(M(h)tz)si)-(1-∑i=1N‍(M(h)t1-1)si))z-((1-∑i=1N‍(M(h)tz-1)si)hhh-(1-∑i=1N‍(M(h)t1-1)si))z-((1-∑i=1N‍(M(h)tz)si)-(1-∑i=1N‍(M(h)t1)si))z+((1-∑i=1N‍(M(h)tz-1)si)hhh-(1-∑i=1N‍(M(h)t1)si))z,
where t1,t2=1,2,….(2) Distributions of
R
z
=
T
s
h
(
z
)
-
T
s
h
(
1
)
.When Tsh(1)=Tsh(z),
(19)P(Rz=0)=∑t=0∞‍(p(t))z=∑t=0∞‍(∑i=1N‍(M(h)t-1-M(h)t)si)z.WhenTsh(1)<Tsh(z),
(20)P(Rz=rz)=∑t1=1∞‍P(Tsh(1)=t1,Tsh(z)=rz+t1)rz>0=∑t1=1∞‍[((1-∑i=1N‍(M(h)rz+t1)si)hhhhhh-(1-∑i=1N‍(M(h)t1-1)si))zhhhh-((1-∑i=1N‍(M(h)rz+t1-1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1-1)si))zhhhh-((1-∑i=1N‍(M(h)rz+t1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1)si))zhhhh+((1-∑i=1N‍(M(h)rz+t1-1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1)si))z].


### 3.2.3. Moment Analysis of FPT

Consider the following:(21)ETsh(1)=∑t1=0∞‍(1-P(t1))z=∑t1=0∞‍(∑i=1N‍(M(h)t1)si)z,(22)E(Tsh(1))2=2∑t1=0∞‍t1(1-P(t1))z+ETsh(1)=2∑t1=0∞‍t1(∑i=1N‍(M(h)t1)si)z+ETsh(1),V(Tsh(1))=E(Tsh(1))2-(ETsh(1))2=2∑t1=0∞‍t1(∑i=1N‍(M(h)t1)si)z+ETsh(1)(1-ETsh(1)),(23)ETsh(z)=∑tz=0∞‍[1-P(tz)z]=∑tz=0∞‍(1-[1-∑i=1N‍(M(h)tz)si]z),(24)E(Tsh(z))2=2∑tz=0∞‍tz[1-P(tz)z]+ETsh(z)=2∑tz=0∞‍tz(1-[1-∑i=1N‍(M(h)tz)si]z)+ETsh(z),V(Tsh(z))=2∑tz=0∞‍tz(1-[1-∑i=1N‍(M(h)tz)si]z)+ETsh(z)(1-ETsh(z)),(25)ERz=∑t=0∞‍(1-P(t)z-[1-P(t)]z)=∑t=0∞‍(1-[1-∑i=1N‍(M(h)t)si]z-[∑i=1N‍(M(h)t)si]z),(26)V(Rz)=2∑tz=0∞‍∑t1=0tz‍(1-P(tz)z-[1-P(t1)]zhhhhhhh+[P(tz)-P(t1)]z)-ERz(1+ERz).We can investigate general cases ofTsh(i) and (Tsh(i),Tsh(j)), respectively, in a similar way. Distributions, joint distributions, moments, and more characteristics of these FPTs could be easily got, the range Tsh(j)-Tsh(i) as well. The discrete-time results obtained here can also be compared with those for multiple continuous-time random walks. We leave these problems to our future work.


## 3.2.1. Probability Distributions ofTsh(1) and Tsh(z)

P
(
t
)
=
P
(
T
s
h
⩽
t
)
=
∑
α
=
0
t
P
(
T
s
h
=
α
)
=
∑
α
=
0
t
p
(
α
), where p(t) and P(Tsh⩽t) are given by (7) and (8), respectively,
(15)p*(t1)=P(Tsh(1)=t1)=(1-P(t1-1))z-(1-P(t1))z=(∑i=1N‍(M(h)t1-1)si)z-(∑i=1N‍(M(h)t1)si)z,hhhhhhhhhhhhhhhhhhhhhhhhhhhht1=1,2,…,(16)p*(tz)=P(Tsh(z)=tz)=(P(tz))z-(P(tz-1))z=(1-∑i=1N‍(M(h)tz)si)z-(1-∑i=1N‍(M(h)tz-1)si)z,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhtz=1,2,….


## 3.2.2. Joint Distributions of(Tsh(1),Tsh(z)) and Distributions of Rz=Tsh(z)-Tsh(1)

(1) Joint distributions of
(
T
s
h
(
1
)
,
T
s
h
(
z
)
)
.When Tsh(1)=Tsh(z),
(17)P(Tsh(1)=Tsh(z)=t)=(p(t))z=(∑i=1N‍(M(h)t-1-M(h)t)si)z,hhhhhhhhhhhhht=0,1,2,….WhenTsh(1)<Tsh(z),
(18)P(Tsh(1)=t1,Tsh(z)=tz)=(P(tz)-P(t1-1))z-(P(tz-1)-P(t1-1))z-(P(tz)-P(t1))z+(P(tz-1)-P(t1))z=((1-∑i=1N‍(M(h)tz)si)-(1-∑i=1N‍(M(h)t1-1)si))z-((1-∑i=1N‍(M(h)tz-1)si)hhh-(1-∑i=1N‍(M(h)t1-1)si))z-((1-∑i=1N‍(M(h)tz)si)-(1-∑i=1N‍(M(h)t1)si))z+((1-∑i=1N‍(M(h)tz-1)si)hhh-(1-∑i=1N‍(M(h)t1)si))z,
where t1,t2=1,2,….(2) Distributions of
R
z
=
T
s
h
(
z
)
-
T
s
h
(
1
)
.When Tsh(1)=Tsh(z),
(19)P(Rz=0)=∑t=0∞‍(p(t))z=∑t=0∞‍(∑i=1N‍(M(h)t-1-M(h)t)si)z.WhenTsh(1)<Tsh(z),
(20)P(Rz=rz)=∑t1=1∞‍P(Tsh(1)=t1,Tsh(z)=rz+t1)rz>0=∑t1=1∞‍[((1-∑i=1N‍(M(h)rz+t1)si)hhhhhh-(1-∑i=1N‍(M(h)t1-1)si))zhhhh-((1-∑i=1N‍(M(h)rz+t1-1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1-1)si))zhhhh-((1-∑i=1N‍(M(h)rz+t1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1)si))zhhhh+((1-∑i=1N‍(M(h)rz+t1-1)si)hhhhhhh-(1-∑i=1N‍(M(h)t1)si))z].


## 3.2.3. Moment Analysis of FPT

Consider the following:(21)ETsh(1)=∑t1=0∞‍(1-P(t1))z=∑t1=0∞‍(∑i=1N‍(M(h)t1)si)z,(22)E(Tsh(1))2=2∑t1=0∞‍t1(1-P(t1))z+ETsh(1)=2∑t1=0∞‍t1(∑i=1N‍(M(h)t1)si)z+ETsh(1),V(Tsh(1))=E(Tsh(1))2-(ETsh(1))2=2∑t1=0∞‍t1(∑i=1N‍(M(h)t1)si)z+ETsh(1)(1-ETsh(1)),(23)ETsh(z)=∑tz=0∞‍[1-P(tz)z]=∑tz=0∞‍(1-[1-∑i=1N‍(M(h)tz)si]z),(24)E(Tsh(z))2=2∑tz=0∞‍tz[1-P(tz)z]+ETsh(z)=2∑tz=0∞‍tz(1-[1-∑i=1N‍(M(h)tz)si]z)+ETsh(z),V(Tsh(z))=2∑tz=0∞‍tz(1-[1-∑i=1N‍(M(h)tz)si]z)+ETsh(z)(1-ETsh(z)),(25)ERz=∑t=0∞‍(1-P(t)z-[1-P(t)]z)=∑t=0∞‍(1-[1-∑i=1N‍(M(h)t)si]z-[∑i=1N‍(M(h)t)si]z),(26)V(Rz)=2∑tz=0∞‍∑t1=0tz‍(1-P(tz)z-[1-P(t1)]zhhhhhhh+[P(tz)-P(t1)]z)-ERz(1+ERz).We can investigate general cases ofTsh(i) and (Tsh(i),Tsh(j)), respectively, in a similar way. Distributions, joint distributions, moments, and more characteristics of these FPTs could be easily got, the range Tsh(j)-Tsh(i) as well. The discrete-time results obtained here can also be compared with those for multiple continuous-time random walks. We leave these problems to our future work.


## 3.3. MFPT of the First Arriving Walker

Since there is no path with a length shorter thandsh and at least one path with a length equal to dsh from the source to the destination, the FPT of single random walk on networks clearly satisfies P(Tsh<dsh)=0, P(Tsh=dsh)>0, Then, combining with (15) and (21), it is not difficult to obtain the following results:
(27)P(Tsh(1)=dsh)⟶1(z⟶∞),(28)ETsh(1)⟶dsh(z⟶∞),(29)VTsh(1)⟶0(z⟶∞).That is to say, the first arriving walker of MRW will take the shortest path or near shortest path with high probability if the walker number is large enough.


## 3.4. MFPT of the Last Arriving Walker

How long does one have to walk before he sees all nodes or traverse all edges in a network? The answer to this question is the vertex CT and edge CT. In the following, we mainly consider the coverage problem of single random walks on a simple network by using numerical simulation. For a simple random walk on a simple general network, the better upper bound of the mean vertex cover time isO(|V||E|) [25], which is well verified by the simulations.An interesting problem is what the number of walkersz will arrive at when the MFPT of the last arriving walker has a consensus with or exceeds the mean cover time of corresponding single random walks. To address this problem, the paper that only gives the simulation analysis. We find the MFPT of the last arriving walker will be significantly more than the mean cover time ECVs and ECEs, when walker number z is network size N of several orders of magnitude, that is, z=N×10k.


## 4. Simulations and Discussions

In this section, for both MPRW and MSRW, we make numerical simulations to deepen our discussion as well as to confirm analytic results. We use a small random network, generated by the Erdös-Rényi model [14], to test the FPT properties of the first and last arriving walkers, respectively, and their relationship as well. If the MRW is being as the search strategy, the FPT of the first arriving walker, to a certain extent, characterizes the search efficiency while that of the last arriving walker depicts network searchability. We demonstrate that wandering walkers are able to utilize and detect the shortest paths and avoid the worst routings. In addition, we explore the cover time of single random walks, which is closely related to the MFPT of the last arriving walker and can be regarded as a performance indicator of network search.We define a small random graph asN=21 labelled nodes and every pair of the nodes is being connected with probability p=0.1 by using the ER model. The average degree of the simple random network is 58/21, namely, 〈d〉=58/21. We choose a pair of nodes as the source and the destination; the source is marked as s=16 and its degree k16=1 and the destination, h=21 and k21=3. The distance between them is 6 steps, dsh=6. The walkers start from a node to reach a given node on the network according to different random-walk strategies. We perform MPRW and MSRW on the simple random network, respectively. Numerical data presented in the figures have been averaged over 104 runs using different number of wandering walkers. The walker number z increases from 5 to 400. Moreover, we carry out single PRW and single SRW starting at s on the simple random network. Simulations state that the mean vertex cover time ECVs=244.985 and the mean edge cover time ECEs=262.445 for the single PRW, while ECVs=676.97 and ECEs=691.7 for the single SRW. In the following diagrams of the probability distributions, the vertical coordinate unit is percentage (%).


### 4.1. MPRW on a Simple Random Network

We record the FPT of the wandering walker, that is, the number of steps before the destination node is visited, starting from the source node. If all the walkers reach the destination, a round of the trial is over. We carry out104 rounds of trials and then analyze the statistical data. We calculate frequencies of the FPT of the first and last arriving walkers for MPRW with 10 walkers on the simple network, which are depicted in Figure 1. We can explore MPRW with 30 walkers in the same way; the numerical result is shown in Figure 2. We can also get the corresponding theoretical result for MPRW with 10 walkers and 30 walkers using (15) and (16) under the same condition. Simulation results confirm our analytic predictions.(a) Distribution of FPT of the first arriving walker for MPRWP(Tsh(1)=t1),  t1∈[0,45]. (b) Distribution of FPT of the last arriving walker for MPRW P(Tsh(z)=tz),  tz∈[0,470]. Here walker number z=10.
(a)
(b)(a) Distribution of FPT of the first arriving walker for MPRWP(Tsh(1)=t1),  t1∈[0,25]. (b) Distribution of FPT of the last arriving walker for MPRW P(Tsh(z)=tz),  tz∈[0,550]. Here walker number z=30.
(a)
(b)We observe that for MPRW with 30 walkers, the probability of the first arriving walker utilizing the shortest path isP(Tsh(1)=6)=0.2373, while for MPRW with 10 walkers the probability P(Tsh(1)=6)=0.0871. The obvious gap can be seen in Figures 2(a) and 1(a). There is a significant increase in the probability of the first arriving walker taking the shortest path. If we use more walkers, the probability will be higher. This agrees with (27). Comparing with Figure 1(a), we can observe in Figure 2(a) that the distribution curve of first passage time peaks up towards t1=6 and mainly concentrates in the interval t1∈[6,20], else t1>25, the probability P(Tsh(1)=t1)=0 for MPRW with 30 walkers. This implies that the first arriving walker will utilize the shortest path or near shortest paths with high probability. In fact, we can calculate the probability of the first arriving walker taking near shortest paths with a length L≤10 by (15), P(Tsh(1)≤10)=0.8443 also as shown in Figure 2(a). That’s to say, if we put 30 walkers on the network, the first arriving walker will almost surely take paths with a path length not more than 10. This observation has deeper meanings. On one hand, we can mark the nodes and the paths of the first arriving walker of MPRW visited, then we can detect the unknown shortest paths between two selected nodes. This is practical significance of realizing optimal routing on networks, especially the mobile ad hoc sensor networks. On the other hand, with a specified source and a walker number z large enough, we conjecture that the wandering walkers will cover the vast majority of the network within O(D) steps with high probability because we can treat any other node as the destination. D is the diameter of the network, which is the maximum distance measured on all pairs of nodes in the network. Consequently, based on the local information of the degrees of current node’s neighbours, the MPRW could be a mechanism of performing efficient search for networks, particularly for the highly heterogeneous small-world networks [14].Considering the MRW as the search strategy, the FPT of the first arriving walker characterizes the search efficiency while that of the last arriving walker depicts network searchability. For MPRW with 10 walkers, we can see that the FPT of the last arriving walker is mainly distributed in the interval[35,424], namely, Tsh(z)∈[35,424] in Figure 1(b) and the corresponding MFPT is 〈Tsh(z)〉=131.818 in Figure 3(b). For MPRW with 30 walkers, we observe that Tsh(z)∈[62,482] in Figure 2(b), 〈Tsh(z)〉=176.596 in Figure 3(b), and the sample standard deviation of Tsh(z)std=54.576. These results can also be computed by (23) and (24). From Figure 3(b), we can see that as the walker number z increases from 5 to 30, the MFPT of the last arriving walker increases fast, whereas z is greater than 30, the MFPT increases slowly. The phenomenon that its growth rate is very small reflects the distribution of FPT which tends to be relatively centralized. At the same time, when the walker number z is more than 30, with z increasing, the sample standard deviation of Tsh(z) tends downwards, as shown in Table 1. Further, we also operate 104 rounds of trials with 107 walkers and analyze the distribution of Tsh(z) according to the statistical data. We find that Tsh(z) only takes 7 numbers such as 655, 664, 697, 699, 710, 727, and 871, and its sample standard deviation is only 40.338. Moreover, Tsh(z) is concentrated in 697, 699, 710, and 727, and the sum of the probabilities taking these four numbers is up to 0.8. This observation agrees with the significant increase in the probability of the first arriving walker taking the shortest path with a small increment in the walker number. We can also record traces of the last arriving walker and the traces containing bad cases of routings. Then, for instance, when designing the routing algorithm for one mobile wireless sensor network, based on local information, we can avoid poor routings of the last arriving walker and improve the reliability of the routing algorithm by MRW.Table 1
Sample standard deviation ofTsh(z) with different walker number.
Walker number
20
30
40
100
400
std ofTsh(z)
54.9625
54.576
54.0093
52.6177
52.558(a) MFPT of the first arriving walker for MPRW〈Tsh(1)〉 versus walker number z. (b) MFPT of the last arriving walker for MPRW 〈Tsh(z)〉 versus walker number z. (c) Range 〈Tsh(z)〉-〈Tsh(1)〉 versus walker number z.
(a)
(b)
(c)We can compute by (21) the MFPT of the first arriving walker 〈Tsh(1)〉 for MPRW with a different walker number z; see Figure 3(a). From Figure 3(a), we can see that with the walker number z increasing from 5 to 400, 〈Tsh(1)〉 decreases from 16.537 to 6.03. 〈Tsh(1)〉 monotonically decreases with walker number z increasing, and it will converge to the distance 6 when z→∞. This further confirms the analytic prediction of (28). It can also be seen that 〈Tsh(1)〉 decreases sharply in the interval z∈[5,30]. That is to say, a small increment in the number of walkers will enable the MFPT to decline substantially in the initial stage. This observation also holds in the case of MSRW [24, 26], which highlights its obvious practical meaning. For example, in [26], for one unstructured peer-to-peer network, the authors propose a MSRW query algorithm that resolves queries almost as fast as the flooding method while reducing network traffic much more in many cases. In the algorithm they use only 16–64 walkers while the network size is 4736–10,000. Their experimental practice is in accordance with our analysis here. The difference is that the query here may be faster since we conduct MPRW on networks.We can also calculate by (23) the MFPT of the last arriving walker 〈Tsh(z)〉 for MPRW with a different walker number z; see Figure 3(b). From Figure 3(b), when z is more than 30, the MFPT increases slowly with z increasing. This has been mentioned above when discussing the sample standard deviation of Tsh(z) and is consistent with that the MFPT of the first arriving walker is declining substantially in the initial stage z∈[5,30]. In addition, we can compute by (25) the range 〈Tsh(z)〉-〈Tsh(1)〉; see Figure 3(c). From Figure 3, we can see that the range mainly depends on 〈Tsh(z)〉. Unlike 〈Tsh(1)〉, we cannot determine the convergence of 〈Tsh(z)〉. However, we can explore the relationship between it and the mean cover time of single PRW, as well as the bounds on 〈Tsh(z)〉. Actually, 〈Tsh(z)〉 hardly exceeds ECEs or ECVs, unless z≫N. From Figure 3(b), when z=400, almost 20 times the size of network N, 〈Tsh(z)〉=284.591 is significantly larger than ECEs=262.445 and ECVs=244.985. To some extent, the FPT and MFPT of the last arriving walker characterize network searchability [7]. In fact, for the complex networks with the same sizes and different topologies, with a specified source and a walker number under the same conditions, we carry out single and multiple random walks on them. The greater the quantities of 〈Tsh(z)〉 and the mean CT, the more difficult to search for the network.


### 4.2. MSRW on a Simple Random Network: Comparison to MPRW

We make comparative study of MSRW and MPRW in the following aspects. Numerical results of the FPT of the first and last arriving walkers for MSRW with 10 and 30 walkers are demonstrated in Figures4 and 5. The corresponding analytic results can be obtained by (15) and (16).(a) Distribution of FPT of the first arriving walker for MSRWP(Tsh(1)=t1), t1∈[0,70]. (b) Distribution of FPT of the last arriving walker for MSRW P(Tsh(z)=tz), tz∈[0,680]. Here walker number z=10.
(a)
(b)(a) Distribution of FPT of the first arriving walker for MSRWP(Tsh(1)=t1),  t1∈[0,35]. (b) Distribution of FPT of the last arriving walker for MSRW P(Tsh(z)=tz),  tz∈[0,710]. Here walker number z=30.
(a)
(b)From Figures5(a) and 4(a), we see that for MSRW with 30 walkers, the probability of the first arriving walker taking the shortest path is P(Tsh(1)=6)=0.0717, while for MSRW with 10 walkers the probability is P(Tsh(1)=6)=0.0251. This observation is similar to the case of MPRW, but the gap is not so apparent here. The first arriving walker will take the shortest path or near shortest paths with high probability P(Tsh(1)≤10)=0.4872; see Figure 5(a). However, comparing with MPRW, the probability 0.4872 here is much smaller than 0.8443; see Figure 2(a).We are able to compute by (21) the MFPT of the first arriving walker 〈Tsh(1)〉 for MSRW with a different walker number z; see Figure 6(a). From Figure 6(a), we can see that with the walker number z increasing from 5 to 400, 〈Tsh(1)〉 decreases from 22.706 to 6.595. 〈Tsh(1)〉 monotonically decreases with walker number z increasing, and it will converge to the distance between the selected two nodes when z→∞. It can also be seen that 〈Tsh(1)〉 decreases sharply in the initial interval z∈[5,50]. The results are consistent with MPRW. The difference is that the decreasing rate and the convergence speed of 〈Tsh(1)〉 in the case of MSRW are much smaller than MPRW; see Figures 6(a) and 3(a).(a) MFPT of the first arriving walker for MSRW〈Tsh(1)〉 versus walker number z. (b) MFPT of the last arriving walker for MSRW 〈Tsh(z)〉 versus walker number z. (c) Range 〈Tsh(z)〉-〈Tsh(1)〉 versus walker number z.
(a)
(b)
(c)As shown in Figures4(b) and 5(b), for the distribution of Tsh(z) of MSRW, it is relatively concentrated in the case of z=30, comparing with z=10. Numerical simulations show that when the walker number z is more than 50, with z increasing, the sample standard deviation of Tsh(z) tends downwards. Comparing Figures 4(b) and 5(b) with Figures 1(b) and 2(b), with the same walker number z, we find that the distribution of Tsh(z) of MSRW is more decentralized than MPRW, while the MFPT 〈Tsh(z)〉 of MSRW is much greater than MPRW; see Figures 6(b) and 3(b).We can also calculate by (23) the MFPT of the last arriving walker 〈Tsh(z)〉 for MSRW with a different walker number z; see Figure 6(b). When z is more than 50, the MFPT increases slowly with z increasing. In addition, we can compute by (25) the range 〈Tsh(z)〉-〈Tsh(1)〉 and find that the range mainly depends on 〈Tsh(z)〉; see Figure 6(c). From Figure 6(b), when z=103, 〈Tsh(z)〉=623.985<ECEs=691.7020; when z=106, almost 5×104 times the size of network N. 〈Tsh(z)〉=743.012 is just significantly greater than ECEs and ECVs. These tell that it is at lower cost to understand network searchability by MPRW than by MSRW.In short, the MPRW search strategy here is more effective and feasible than MSRW. This is due to the fact that the MPRW strategy is prone to searching for high-degree nodes. In other words, if we start from a periphery (or low-degree) node and search for a hub (or high-degree) node on networks, we need only a small number of wandering walkers and a small number of steps by the MPRW strategy, which also offers one efficient way of detecting hub nodes in scale-free networks [14].


## 4.1. MPRW on a Simple Random Network

We record the FPT of the wandering walker, that is, the number of steps before the destination node is visited, starting from the source node. If all the walkers reach the destination, a round of the trial is over. We carry out104 rounds of trials and then analyze the statistical data. We calculate frequencies of the FPT of the first and last arriving walkers for MPRW with 10 walkers on the simple network, which are depicted in Figure 1. We can explore MPRW with 30 walkers in the same way; the numerical result is shown in Figure 2. We can also get the corresponding theoretical result for MPRW with 10 walkers and 30 walkers using (15) and (16) under the same condition. Simulation results confirm our analytic predictions.(a) Distribution of FPT of the first arriving walker for MPRWP(Tsh(1)=t1),  t1∈[0,45]. (b) Distribution of FPT of the last arriving walker for MPRW P(Tsh(z)=tz),  tz∈[0,470]. Here walker number z=10.
(a)
(b)(a) Distribution of FPT of the first arriving walker for MPRWP(Tsh(1)=t1),  t1∈[0,25]. (b) Distribution of FPT of the last arriving walker for MPRW P(Tsh(z)=tz),  tz∈[0,550]. Here walker number z=30.
(a)
(b)We observe that for MPRW with 30 walkers, the probability of the first arriving walker utilizing the shortest path isP(Tsh(1)=6)=0.2373, while for MPRW with 10 walkers the probability P(Tsh(1)=6)=0.0871. The obvious gap can be seen in Figures 2(a) and 1(a). There is a significant increase in the probability of the first arriving walker taking the shortest path. If we use more walkers, the probability will be higher. This agrees with (27). Comparing with Figure 1(a), we can observe in Figure 2(a) that the distribution curve of first passage time peaks up towards t1=6 and mainly concentrates in the interval t1∈[6,20], else t1>25, the probability P(Tsh(1)=t1)=0 for MPRW with 30 walkers. This implies that the first arriving walker will utilize the shortest path or near shortest paths with high probability. In fact, we can calculate the probability of the first arriving walker taking near shortest paths with a length L≤10 by (15), P(Tsh(1)≤10)=0.8443 also as shown in Figure 2(a). That’s to say, if we put 30 walkers on the network, the first arriving walker will almost surely take paths with a path length not more than 10. This observation has deeper meanings. On one hand, we can mark the nodes and the paths of the first arriving walker of MPRW visited, then we can detect the unknown shortest paths between two selected nodes. This is practical significance of realizing optimal routing on networks, especially the mobile ad hoc sensor networks. On the other hand, with a specified source and a walker number z large enough, we conjecture that the wandering walkers will cover the vast majority of the network within O(D) steps with high probability because we can treat any other node as the destination. D is the diameter of the network, which is the maximum distance measured on all pairs of nodes in the network. Consequently, based on the local information of the degrees of current node’s neighbours, the MPRW could be a mechanism of performing efficient search for networks, particularly for the highly heterogeneous small-world networks [14].Considering the MRW as the search strategy, the FPT of the first arriving walker characterizes the search efficiency while that of the last arriving walker depicts network searchability. For MPRW with 10 walkers, we can see that the FPT of the last arriving walker is mainly distributed in the interval[35,424], namely, Tsh(z)∈[35,424] in Figure 1(b) and the corresponding MFPT is 〈Tsh(z)〉=131.818 in Figure 3(b). For MPRW with 30 walkers, we observe that Tsh(z)∈[62,482] in Figure 2(b), 〈Tsh(z)〉=176.596 in Figure 3(b), and the sample standard deviation of Tsh(z)std=54.576. These results can also be computed by (23) and (24). From Figure 3(b), we can see that as the walker number z increases from 5 to 30, the MFPT of the last arriving walker increases fast, whereas z is greater than 30, the MFPT increases slowly. The phenomenon that its growth rate is very small reflects the distribution of FPT which tends to be relatively centralized. At the same time, when the walker number z is more than 30, with z increasing, the sample standard deviation of Tsh(z) tends downwards, as shown in Table 1. Further, we also operate 104 rounds of trials with 107 walkers and analyze the distribution of Tsh(z) according to the statistical data. We find that Tsh(z) only takes 7 numbers such as 655, 664, 697, 699, 710, 727, and 871, and its sample standard deviation is only 40.338. Moreover, Tsh(z) is concentrated in 697, 699, 710, and 727, and the sum of the probabilities taking these four numbers is up to 0.8. This observation agrees with the significant increase in the probability of the first arriving walker taking the shortest path with a small increment in the walker number. We can also record traces of the last arriving walker and the traces containing bad cases of routings. Then, for instance, when designing the routing algorithm for one mobile wireless sensor network, based on local information, we can avoid poor routings of the last arriving walker and improve the reliability of the routing algorithm by MRW.Table 1
Sample standard deviation ofTsh(z) with different walker number.
Walker number
20
30
40
100
400
std ofTsh(z)
54.9625
54.576
54.0093
52.6177
52.558(a) MFPT of the first arriving walker for MPRW〈Tsh(1)〉 versus walker number z. (b) MFPT of the last arriving walker for MPRW 〈Tsh(z)〉 versus walker number z. (c) Range 〈Tsh(z)〉-〈Tsh(1)〉 versus walker number z.
(a)
(b)
(c)We can compute by (21) the MFPT of the first arriving walker 〈Tsh(1)〉 for MPRW with a different walker number z; see Figure 3(a). From Figure 3(a), we can see that with the walker number z increasing from 5 to 400, 〈Tsh(1)〉 decreases from 16.537 to 6.03. 〈Tsh(1)〉 monotonically decreases with walker number z increasing, and it will converge to the distance 6 when z→∞. This further confirms the analytic prediction of (28). It can also be seen that 〈Tsh(1)〉 decreases sharply in the interval z∈[5,30]. That is to say, a small increment in the number of walkers will enable the MFPT to decline substantially in the initial stage. This observation also holds in the case of MSRW [24, 26], which highlights its obvious practical meaning. For example, in [26], for one unstructured peer-to-peer network, the authors propose a MSRW query algorithm that resolves queries almost as fast as the flooding method while reducing network traffic much more in many cases. In the algorithm they use only 16–64 walkers while the network size is 4736–10,000. Their experimental practice is in accordance with our analysis here. The difference is that the query here may be faster since we conduct MPRW on networks.We can also calculate by (23) the MFPT of the last arriving walker 〈Tsh(z)〉 for MPRW with a different walker number z; see Figure 3(b). From Figure 3(b), when z is more than 30, the MFPT increases slowly with z increasing. This has been mentioned above when discussing the sample standard deviation of Tsh(z) and is consistent with that the MFPT of the first arriving walker is declining substantially in the initial stage z∈[5,30]. In addition, we can compute by (25) the range 〈Tsh(z)〉-〈Tsh(1)〉; see Figure 3(c). From Figure 3, we can see that the range mainly depends on 〈Tsh(z)〉. Unlike 〈Tsh(1)〉, we cannot determine the convergence of 〈Tsh(z)〉. However, we can explore the relationship between it and the mean cover time of single PRW, as well as the bounds on 〈Tsh(z)〉. Actually, 〈Tsh(z)〉 hardly exceeds ECEs or ECVs, unless z≫N. From Figure 3(b), when z=400, almost 20 times the size of network N, 〈Tsh(z)〉=284.591 is significantly larger than ECEs=262.445 and ECVs=244.985. To some extent, the FPT and MFPT of the last arriving walker characterize network searchability [7]. In fact, for the complex networks with the same sizes and different topologies, with a specified source and a walker number under the same conditions, we carry out single and multiple random walks on them. The greater the quantities of 〈Tsh(z)〉 and the mean CT, the more difficult to search for the network.


## 4.2. MSRW on a Simple Random Network: Comparison to MPRW

We make comparative study of MSRW and MPRW in the following aspects. Numerical results of the FPT of the first and last arriving walkers for MSRW with 10 and 30 walkers are demonstrated in Figures4 and 5. The corresponding analytic results can be obtained by (15) and (16).(a) Distribution of FPT of the first arriving walker for MSRWP(Tsh(1)=t1), t1∈[0,70]. (b) Distribution of FPT of the last arriving walker for MSRW P(Tsh(z)=tz), tz∈[0,680]. Here walker number z=10.
(a)
(b)(a) Distribution of FPT of the first arriving walker for MSRWP(Tsh(1)=t1),  t1∈[0,35]. (b) Distribution of FPT of the last arriving walker for MSRW P(Tsh(z)=tz),  tz∈[0,710]. Here walker number z=30.
(a)
(b)From Figures5(a) and 4(a), we see that for MSRW with 30 walkers, the probability of the first arriving walker taking the shortest path is P(Tsh(1)=6)=0.0717, while for MSRW with 10 walkers the probability is P(Tsh(1)=6)=0.0251. This observation is similar to the case of MPRW, but the gap is not so apparent here. The first arriving walker will take the shortest path or near shortest paths with high probability P(Tsh(1)≤10)=0.4872; see Figure 5(a). However, comparing with MPRW, the probability 0.4872 here is much smaller than 0.8443; see Figure 2(a).We are able to compute by (21) the MFPT of the first arriving walker 〈Tsh(1)〉 for MSRW with a different walker number z; see Figure 6(a). From Figure 6(a), we can see that with the walker number z increasing from 5 to 400, 〈Tsh(1)〉 decreases from 22.706 to 6.595. 〈Tsh(1)〉 monotonically decreases with walker number z increasing, and it will converge to the distance between the selected two nodes when z→∞. It can also be seen that 〈Tsh(1)〉 decreases sharply in the initial interval z∈[5,50]. The results are consistent with MPRW. The difference is that the decreasing rate and the convergence speed of 〈Tsh(1)〉 in the case of MSRW are much smaller than MPRW; see Figures 6(a) and 3(a).(a) MFPT of the first arriving walker for MSRW〈Tsh(1)〉 versus walker number z. (b) MFPT of the last arriving walker for MSRW 〈Tsh(z)〉 versus walker number z. (c) Range 〈Tsh(z)〉-〈Tsh(1)〉 versus walker number z.
(a)
(b)
(c)As shown in Figures4(b) and 5(b), for the distribution of Tsh(z) of MSRW, it is relatively concentrated in the case of z=30, comparing with z=10. Numerical simulations show that when the walker number z is more than 50, with z increasing, the sample standard deviation of Tsh(z) tends downwards. Comparing Figures 4(b) and 5(b) with Figures 1(b) and 2(b), with the same walker number z, we find that the distribution of Tsh(z) of MSRW is more decentralized than MPRW, while the MFPT 〈Tsh(z)〉 of MSRW is much greater than MPRW; see Figures 6(b) and 3(b).We can also calculate by (23) the MFPT of the last arriving walker 〈Tsh(z)〉 for MSRW with a different walker number z; see Figure 6(b). When z is more than 50, the MFPT increases slowly with z increasing. In addition, we can compute by (25) the range 〈Tsh(z)〉-〈Tsh(1)〉 and find that the range mainly depends on 〈Tsh(z)〉; see Figure 6(c). From Figure 6(b), when z=103, 〈Tsh(z)〉=623.985<ECEs=691.7020; when z=106, almost 5×104 times the size of network N. 〈Tsh(z)〉=743.012 is just significantly greater than ECEs and ECVs. These tell that it is at lower cost to understand network searchability by MPRW than by MSRW.In short, the MPRW search strategy here is more effective and feasible than MSRW. This is due to the fact that the MPRW strategy is prone to searching for high-degree nodes. In other words, if we start from a periphery (or low-degree) node and search for a hub (or high-degree) node on networks, we need only a small number of wandering walkers and a small number of steps by the MPRW strategy, which also offers one efficient way of detecting hub nodes in scale-free networks [14].


## 5. Conclusions

Some theoretical and technological problems with relation to MRW on networks have been investigated in this paper. These problems mainly come from random-walk theory and network search application. We mainly discussed the behaviors of the first and last arriving walkers of MRW on networks. We made use of random walks on weighted graphs to study single random walks on networks and took advantage of the order statistics approach to investigate MRW on networks, which can be a framework of random walks on networks. We analyzed the FPT and MFPT of MPRW on networks, making comparative studies with MSRW. We explored the FPT of the first and last arriving walkers and presented the corresponding equations of the probability distributions and moments. The MFPT of the first arriving walker monotonically decreases with walker numberz increasing, and it will converge to the distance between source node and destination node. Furthermore, a small increment in the number of walkers will enable the MFPT of the first arriving walker to decrease sharply in the initial stage and the distribution curve of the FPT of the first arriving walker to peak up towards the distance between the selected two nodes as well. Thus, if the walker number is properly set, the first arriving walker will take the shortest path or near shortest paths with high probability. With the walker number increasing, the MFPT of the last arriving walker also increases substantially in the initial stage. The MFPT of the last arriving walker is closely related with the mean CT of the corresponding single random walk. It could be seen that the MFPT of the last arriving walker is difficult to exceed the mean cover time unless z≫N.Numerical simulations of an ensemble of random walkers moving on a paradigmatic network model confirmed analytical predictions and deepened discussions. In addition, by MRW on networks, we investigated some practical search-related issues. The MRW regarded as the search strategy, then the FPT of the first arriving walker characterizes the search efficiency while that of the last arriving walker portrays network searchability. Accordingly, the mean CT of single random walks can also be considered as a performance indicator of network search. We can detect unknown shortest paths by the first arriving walker and avoid poor routings by last arriving walker, which is of practical significance for realizing optimal routing and performing efficient searching on networks. MSRW and MPRW being search strategies on networks, MPRW prefers the high-degree nodes, while MSRW searches for the relatively low-degree nodes more efficiently. This inspires us to develop proper MRW for identification of influential spreaders in complex networks [27], including hub nodes in the highly heterogeneous networks and congestion bottlenecks in the urban traffic networks. We leave these interesting problems to our future work. Finally, we point out that MPRW and MSRW could complement each other in web search, routing, communication transmission, transportation, and other applications, thereby increasing the efficiency and reliability of the search-related processes.



---

*Source: 734630-2013-12-12.xml*