Multiple random walksare the movement of several independent random walkers on a graph , and are applied to various graph algorithms. In order to design an efficient graph algorithm based on multiple random walks , it is essential to study multiple random walks theoretically for deeply understanding their characteristics. The first meeting time is one of the important metrics for the multiple random walks. The first meeting time on a graph is defined by the time it takes for multiple random walkers to meet at the same node in graph. The first meeting time is closely related to the rendezvous problem, which is are a fundamental problem in the field of computer science. In previous works, the first meeting time of multiple random walks has been analyzed . However, many of these previous works focus on regular graphs. In this paper, we analyze the first meeting time of multiple random walks in arbitrary graphs , and clarify the effect of graph structures on its expected value . First, we derive the spectral formula of the expected first meeting time on the basis of the spectral graph theory. Then, we examine the principal component of the expected first meeting time using the derived spectral formula. The clarified principal component reveals that (a)the expected first meeting time is almost dominated by n/(1+d_{\rm std}^2/d_{\rm avg}^2) and (b)the expected first meeting time is independent of the starting nodes of random walkers  where n is the number of nodes of the graph. d_{\rm avg} and d_{\rm std} are the mean and the standard deviation of weighted node degrees, respectively. The characteristics (a) is useful to understand the effect of the graph structure on the first meeting time. According to the revealed effect of graph structures, the variance of  coefficient d_{\rm std}/d_{\rm avg}(degree heterogeneity) for weighted degrees facilitates quicker the meeting of random walkers.
Various graph algorithms have been developed with multiple random walks, the movement of several independent random walkers on a graph . Designing an efficient graph algorithm based on multiple random walks requires investigating multiple random walks theoretically to attain a deep understanding of their characteristics. The first meeting time is one of the important metrics for multiple random walks. The first meeting time on a graph is defined by the time it takes for multiple random walkers to meet at the same node in a graph. This time is closely related to the rendezvous problem, a fundamental problem in computer science. The first meeting time of multiple random walks has been analyzed previously, but many of these analyses have focused on regular graphs. In this paper, we analyze the first meeting time of multiple random walks in arbitrary graphs and clarify the effects of graph structures on expected values . First, we derive the spectral formula of the expected first meeting time on the basis of spectral graph theory. Then, we examine the principal component of the expected first meeting time using the derived spectral formula. The clarified principal component reveals that (a)the expected first meeting time is almost dominated by n/(1+d_{\rm std}^2/d_{\rm avg}^2) and (b)the expected first meeting time is independent of the starting nodes of random walkers , where n is the number of nodes of the graph. d_{\rm avg} and d_{\rm std} are the average and the standard deviation of weighted node degrees, respectively. The characteristic (a) is useful for understanding the effect of the graph structure on the first meeting time. According to the revealed effect of graph structures, the variance of the coefficient d_{\rm std}/d_{\rm avg}(degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.
R
Multiple random walksare
Various graph algorithms have been developed with multiple random walks,
R
, and are applied to various graph algorithms. In order to design
. Designing
R
, it is essential to study
requires investigating
R
for deeply understanding
to attain a deep understanding of
D
the
R
graph. The first meeting
a graph. This
D
which is are
D
the field of
R
In previous works, the
The
R
. However,
previously, but
R
previous works focus
analyses have focused
D
,
R
effect
effects
R
its expected value
expected values
D
the
A
,
R
mean
average
R
characteristics
characteristic
R
to understand
for understanding
A
the
D
quicker