  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.
