Multiple random walks is a model for movement of several independent random walkers on a graph, and it is applied to various graph algorithms. In order to design an efficient graph algorithm using multiple random walks, it is essential to study theoretical considerations for deeply understanding the characteristicsof graph algorithms . The first meeting time is one of the important metrics for the multiple random walks. The first meeting time is defined as the time it takes for multiple random walkers to meet on a same node . The first meeting time is closely related to the rendezvous problem . In various works, the first meeting time of multiple random walk has been analyzed. However, many of these previous works focused on regular graphs. In this paper, we analyze  first meeting time of multiple random walks in arbitrary graph , and clarify the effect of graph structures on its expected value. First, we derive the spectral formula for the expected first meeting time of two random walkers using the spectral graph theory. Then,  the principal component of the expected first meeting time are examined using the derived spectral formula. The resulting 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 beginning nodes of multiple random walks where n is the number of nodes  . d_{\rm avg} and d_{\rm std} are the mean and  standard deviation of the weighted degree of each node , respectively. n and d_{\rm avg, and d_{\rm std} are related to the statistics of graph structures}  . According to the analysis result , the variance of coefficient for weighted degrees, d_{\rm std}/d_{\rm avg}(degree heterogeneity) , facilitates quicker the meeting of random walkers.
Multiple random walks are 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. , and d_{\rm std} are related to the statistics of graph structures} 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.
R
is a model for
are the
R
it is
are
R
using
based on
R
theoretical considerations
multiple random walks theoretically
R
the characteristicsof graph algorithms
their characteristics
R
is defined as
on a graph is defined by
R
on a same node
at the same node in graph
R
. In various
, which is are a fundamental problem in the field of computer science. In previous
R
walk
walks
R
focused
focus
A
the
R
graph
graphs
R
for
of
R
of two random walkers using
on the basis of
A
we examine
D
are examined
R
resulting
clarified
R
beginning nodes of multiple random walks
starting nodes of random walkers
A
of the graph
A
the
R
the weighted degree of each node
weighted node degrees
D
n and d_{\rm avg
A
The characteristics (a) is useful to understand the effect of the graph structure on the first meeting time
R
analysis result
revealed effect of graph structures
D
for weighted degrees,
R
,
for weighted degrees