VOL. E104-B NO. 6
JUNE 2021
The usage of this PDF file must comply with the IEICE Provisions
on Copyright.
The author(s) can distribute this PDF file for research andeducational (nonprofit) purposes only.
Distribution by anyone other than the author(s) is prohibited.

IEICE TRANS. COMMUN., VOL.E104–B, NO.6 JUNE 2021

604

PAPER

Graph Degree Heterogeneity Facilitates Random Walker Meetings∗
Yusuke SAKUMOTO†a) and Hiroyuki OHSAKI†b) , Members

SUMMARY
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 toattain a deep understanding of their characteristics. The first meeting timeis 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 focused on regular graphs. In this paper, weanalyze 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 ofspectral 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
2 /d 2 ) and (b) the expected first meetingalmost dominated by n/(1 + dstd
avg
time is independent of the starting nodes of random walkers, where n is thenumber of nodes of the graph. davg and dstd are the average and the standard deviation of weighted node degrees, respectively. Characteristic (a) isuseful for understanding the effect of the graph structure on the first meeting time. According to the revealed effect of graph structures, the varianceof the coefficient dstd /davg (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.
key words: first meeting time, random walk, spectral graph theory

1.

Introduction

Various graph algorithms have been developed with multiple random walks, the movement of several independent
random walkers on a graph, as a result of graph algorithms
offer ease of analysis and light-weight processing. Notableapplications include (a) a search algorithm for finding a particular node on a graph [1], [2], (b) an algorithm for spreading information across graphs by exchanging information
only between adjacent nodes [3], and (c) the rendezvous algorithm for efficient meeting of multiple random walkers at
the same node [4]. Designing an efficient graph algorithm
based on multiple random walks requires studying multiple random walks theoretically in order to understand theircharacteristics at a deep level.
Manuscript received June 16, 2020.
Manuscript revised November 8, 2020.
Manuscript publicized December 14, 2020.
†
The authors are with Kwansei Gakuin University, Sanda-shi,
669-1337 Japan.
∗
The preprint of this paper is available at https://arxiv.org/abs/
2005.11161.
a) E-mail: sakumoto@kwansei.ac.jpb) E-mail: ohsaki@kwansei.ac.jp
DOI: 10.1587/transcom.2020EBP3093

Several important metrics (e.g., first hitting time, recurrence time, cover time, re-encountering time, and firstmeeting time) have been used for investigating the characteristics of multiple random walks. The first hitting time isthe time it takes for any random walker to arrive at a specified node, and it is important for evaluating the performanceof relevant search algorithms. The recurrence time is thetime required to return any one of the random walkers to
the starting node, and it is thus a particular case of the firsthitting time. The cover time is the time it takes for any
random walker to reach all of the nodes and corresponds
to the maximum value of the first hitting times. The covertime strongly affects the information dissemination speed in
the graph. The re-encountering time and the first meetingtime are the times it takes for multiple random walkers tomeet at the same node. The re-encountering time relates torandom walkers starting from the same node, and the firstmeeting time relates to those starting from different nodes.
In particular, the first meeting time is closely related to therendezvous problem, a fundamental problem in computerscience. The rendezvous problem occurs in a number of engineering problems (e.g., the self-stabilizing token management system problem [5], [6] and the k-server problem [7]).
Designing efficient algorithms for the rendezvous problem
requires clarification of the characteristics of the first meeting time.
The first meeting time of multiple random walks wasanalyzed in [8]–[12]. However, many of these previous
studies focus on regular graphs. In [12], George et al. did
pioneering work on multiple random walks on non-regulargraphs and derived a closed-form formula for calculating
the expected value of the first meeting time in arbitrary
graphs. However, the effects of graph structures on the
expected first meeting time remain unclear. Designing effective algorithms using multiple random walks for realistic
graphs (e.g., social networks and communication networks)
benefits from understanding the effects of graph structureson the expected first meeting time. Since it is difficult toclarify these effects numerically using the closed-form formula derived in [12], the effects must be examined using
analysis of multiple random walks.
In this paper, we analyze the first meeting time of multiple random walks in arbitrary graphs and clarify the effects
of graph structures on its expected value. First, we derive
the spectral formula of the expected first meeting time on
the basis of spectral graph theory that is used to analyze
the characteristics of graphs. Then, we examine the prin-

Copyright c 2021 The Institute of Electronics, Information and Communication Engineers

SAKUMOTO and OHSAKI: GRAPH DEGREE HETEROGENEITY FACILITATES RANDOM WALKER MEETINGS

605

cipal 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 al22most dominated by n/(1 + dstd
/davg), where n is the numberof nodes in the graph and davg and dstd are the average andstandard deviation of weighted node degrees, respectively,and (b) the expected first meeting time is independent of thestarting nodes of random walkers. Characteristic (a) provides understanding of the effect of the graph structure on
the first meeting time. In addition, we verify the validity of
the analysis results through numerical examples using popular random graphs.
The contributions in this paper are summarized as follows.
• We extend the analysis of a single random walks tomultiple random walks using spectral graph theory.
• We derive the spectral formula (40) of the expected firstmeeting time.
• We clarify the principal component of the expected firstmeeting time from Eqs. (62) and (63).
• We reveal the effect of graph structures on the expected
first meeting time from Eq. (63).
• We confirm the validity of the derived spectral formula(40) and the clarified principal component for popular
random graphs with different scales and different structures.
The remainder of this paper is organized as follows.
In Sect. 2, we describe the definition of graphs and random
walks and introduce the previous analysis of a single random walk using spectral graph theory. In Sect. 3, we derive
the spectral formula of the expected first meeting time using
spectral graph theory and clarify the principal componentof the expected first meeting time on the basis of the derived
spectral formula. Section 4 confirms the validity of the analysis results through numerical examples using popular random graphs. Section 5 concludes the paper and discusses
future work.
2.

Preliminary

In this section, we provide the definition of graphs and random walks that we use in our analysis. In addition, we review existing analysis results of a single random walk basedon spectral graph theory.
A graph is given by G = (V, E), where V and E are a
set of nodes and a set of links, respectively. Self-loop links(i, i) for i ∈ V are not included in E. The weight for link(i, j) ∈ E is wi j , where wi j > 0 and wi j = w ji . We denote theset of adjacent nodes of node i ∈ V by ∂i. Letting di be theweighted degree of node i ∈ V, we define di as
X
di :=
wik .
(1)
k∈∂i

We describe a random walk starting from node a ∈ V.
In this random walk, the random walker at node i ∈ V moves
to adjacent node j ∈ ∂i using transition probability pi→ jgiven bypi→ j =

wi j
.
di

(2)

Let xa:i (t) be the probability that a random walker startingfromnode a ∈ V is at node i ∈ V at time t, wherePi∈V xa:i (t) = 1. If Eq. (2) is used, then xa:i (t + 1) isX
xa:i (t + 1) =xa: j (t) p j→i .
(3)
j∈∂i

Using column vector xa (t) = (xa:i (t))i∈V , Eq. (3) for all nodes∀i ∈ V can be written simultaneously asxa (t + 1) = A D−1 xa (t),(4)

where D and A are the degree and adjacency matrices defined as
D := diag(di )i∈V ,(wi j if (i, j) ∈ E,
A :=0otherwise(5)(6)

respectively. A D−1 is the matrix whose (i, j)th element is
the transition probability p j→i . Random walks defined by
Eqs. (3) through (6) are equivalent to those used in [8]–[12],and are applied to search in unstructured P2P networks [1],[2]. Hence, it is worth analyzing these random walks interm of engineering applications. Equation (4) describes the
behavior of the random walk. Since A D−1 is an asymmetricmatrix, Eq. (4) is not easy to handle analytically using linear
algebra. Consequently, we modify Eq. (4) toD−1/2 xa (t + 1) = D−1/2 A D−1/2 D−1/2 xa (t)= W D−1/2 xa (t)x̂a (t + 1) = W x̂a (t),(7)

where W = D−1/2 A D−1/2 and x̂ a (t) = D−1/2 xa (t). Since
W is a symmetric matrix, Eq. (7) is easier to handle thanEq. (4). In general, in spectral graph theory, the behaviorof an analysis target is expressed in terms of a matrix suchas Eq. (7), and the characteristics of the target are analyzed
using the eigenvalues and eigenvectors of the matrix on thebasis of linear algebra.
W can always be diagonalized using the orthogonal
matrix Q that satisfies t Q = Q−1 . Let λk be the kth largest
eigenvalue of W. Note that the maximum eigenvalue λ1 isalways 1. In this paper, we assume that G is connected andnot a bipartite graph. In this case, the eigenvalues λk for
2 ≤ k ≤ n satisfy−1 < λn < · · · < λ2 < 1.

(8)

We let qk be the eigenvector for eigenvalue λk by, with theconsequence that Q is Q = (qk )1≤k≤n . Since Q is an orthogonal matrix, qk and ql for 1 ≤ k, l ≤ n satisfy(
1 if k = ltqk ql =
(9)0 oterwise

IEICE TRANS. COMMUN., VOL.E104–B, NO.6 JUNE 2021

606

In particular, the maximum eigenvector q1 isp
1 p p
q1 = √ t ( d1 , d2 , · · · , dn ),
(10)
s1
P
where s1 = i∈V di . s1 is related to a statistic of the graphstructure of G and can be written by s1 = n davg , where davg
is the average weighted degree.
In [13], Lovász analyzed a single random walk ongraph G on the basis of spectral graph theory. Solving
Eq. (7) in [13] results in the probability xa:i (t) being√ Xndixa:i (t) = √qk (a) qk (i) λtk .
(11)da k=1other words, µa:i corresponds to the search time of node i using the random walk. Therefore, Eq. (15) is also importantfor understanding the characteristics of the search algorithm
using a random walk.
According to [14], when n is sufficiently large, theright-hand side of Eq. (14) is negligibly small in several
graphs (e.g., -graphs, k-nearest neighbor graphs, Gaussian
similarity graphs, and Erdös-Rényi graphs). Considering theresult of [14], we expect that the right-hand side of Eq. (14)is negligibly small in various graph classes.

According to this equation, xa:i (t) can be calculated using
eigenvalues λk and eigenvectors qk . A closed-form formulausing eigenvalues and eigenvectors such as Eq. (11) is referred to as a spectral formula.
∗
Let xa:ibe the limit value of xa:i (t) for t → ∞. From∗
Eq. (11), xa:ican be derived as

In this section, we analyze the expected first meeting time
µa,b of two random walkers starting from node a ∈ V andb ∈ V in graph G on the basis of spectral graph theory. We
first derive the spectral formula of µa,b . Then, we clarify
the principal component of µa,b using the derived spectral
formula. Finally, we reveal the effect of the graph structure
on µa,b on the basis of the clarified principal component.
Our analysis results are important also for understanding the first meeting time T s(nRW ) of nRW random walkers,
where nRW > 2 and s is the vector of starting nodes of nRW
random walkers. This is because T s(nRW ) is strongly affectedby the first meeting time T s(2) of two random walkers. Notethat the expectation of T s(2) with s = (a, b) is correspond toµa,b . To attain an efficient meeting of nRW random walkers,
two of the nRW random walkers must move together after
meeting at the same node. Namely, when two random walkers meet at the same node, they are combined into a single
random walker. Finally, if all of nRW random walkers become a single random walker, the first meeting of them areaccomplished. In this case, the first meeting time T s(nRW ) ofnRW random walkers is obtained as the sum of the first meeting times T s(2) of two random walkers. Consequently, thecharacteristics of the first meeting time T s(nRW ) for nRW random walkers can be expected to be strongly associated withthat of two random walkers.

∗xa:i= lim xa:i (t)
t→∞
√

√ X
n
 didit= lim  √ q1 (i) q1 (a) + √qk (a) qk (i) λk t→∞dada k=2√didi= √ q1 (a) q1 (i) = .
(12)
s1
da

In this derivation process, we used |λk | < 1 for k ≥ 2.
According to Eq. (12), xa:i (t) is roughly proportional to theweighted degree di if sufficient time has elapsed since therandom walker started.
The analysis in [13] derived the expected first hitting
time µa:i , the expected time it takes for a random walker
starting from node a to arrive at node i. From Eq. (11), thespectral formula of expected first hitting time µa:i is derived
as


n
X
1  q2k (i) qk (a) qk (i)  .
µa:i = s1(13)− √1 − λk di
da di
k=2
In [14], the effect of the graph structure on µa:i was clarified using the spectral formula of the expected first hitting
time µa:i . According to [14], µa:i satisfies!
1
1
2 wmax1µa:i −
≤ 2
+1 ,
(14)
s1
di
dmin 1 − λ2where wmax and dmin are the maximum of link weights andthe minimum of weighted degrees, respectively. If the righthand side of Eq. (14) is sufficiently small, the expected firsthitting time µa:i is approximated bys1µa:i ≈ .
(15)
di
In this case, µa:i is almost dominated by s1 /di , with the consequence that s1 /di can be expected to be the principal component of µa:i . According to Eq. (15), µa:i is roughly proportional to s1 , which is a statistic of the graph structure. In

3.

3.1

Analysis

Spectral Formula of Expected First Meeting Time µa,b

We derive the spectral formula of the expected first meetingtime µa,b using the same method as is used to derive thatof the expected first hitting time µa:i in [13]. In [13], thespectral formula was derived using the generating functionof the existing probability xa:i (t). In general, the generating
function F(z) of the probability f (t) isF(z) :=∞
X

f (t)zt ,

(16)

t=0

Note that f (t) is the probability that an event occurs at timet. The existing probability xa:i (t) is anPexample of f (t). If
the probability f (t) is satisfied with ∞t=0 f (t) = 1, using
the generating function F(z), the expectation E(t) with theprobability f (t) isSAKUMOTO and OHSAKI: GRAPH DEGREE HETEROGENEITY FACILITATES RANDOM WALKER MEETINGS

607

E(t) =∞Xt f (t) =

t=1

dF(z)
.
dz z=1(17)

Importantly, even if we do not know the closed-form formula of the probability f (t), we can still derive the expectation E(t) using the generating function F(z) on the basis of
the above equation. We first discuss the generating functionof the first meeting probability. Without the value of the firstmeeting probability, we then derive the spectral formula ofthe expected first meeting time µa,b by substituting the generating function obtained into Eq. (17).
Let ra,b:c (t) be the probability that two random walkers
first meet at node c at time t. Since two random walkers canmeet at any node, the first meeting probability ra,b:∗ (t) isXra,b:∗ (t) =ra,b:c (t).
(18)

Fig. 1

Random walks starting from nodes a and b from time 0 to time t.

tXxa,b:∗ (t) =ra,b:∗0 (s) x∗0 ,∗0 :∗ (t − s).

(21)

s=0

Using the probability xc0 ,c0 :c (t) that the two random walkers
starting at node c0 ∈ V at time 0 meet again at node c ∈ V attime t, we approximately set x∗0 ,∗0 :∗ (t) asc∈V

In ra,b:∗ (t), the symbol ∗ designates any node in V. Deriving
the spectral formula of the expected first meeting time µa,b
using Eq. (17) requires the generating function Ra,b:∗ (z) ofra,b:∗ (t).
The probabilities that the two random walkers are atnode i at time t are xa:i (t) and xb:i (t), respectively. Since thespectral formulas of xa:i (t) and xb:i (t) are given by Eq. (11),the generating functions of xa:i (t) and xb:i (t) can be derived
using Eq. (16). However, since it is not easy to obtain the
spectral formula of ra,b:∗ (t), we obtain the generating function Ra,b:∗ (z) of ra,b:∗ (t) from those of xa:i (t) and xb:i (t) andthen derive the spectral formula of the expected first meeting time µa,b using Eq. (17).
With the aim of obtaining the generating function
Ra,b:∗ (z) of the first meeting probability ra,b:∗ (t), we discuss the relationship between ra,b:∗ (t), xa:i (t) and xb:i (t). Let
xa,b:c (t) be the probability that the two random walker meetat the same node c ∈ V at time t. The meeting probability
xa,b:∗ (t) at any node isXxa,b:∗ (t) =xa,b:c (t).
(19)
Since each random walker moves independently, xa,b:∗ (t) isXXxa,b:∗ (t) =xa,b:c (t) =xa:c (t) xb:c (t).
(20)
c∈V

xa,b:∗ (t) includes both the first meeting probability ra,b:∗ (t)and also the probability of the second and subsequent meetings. Hence, as shown in Fig. 1, we divide the transition of
the two random walks from time 0 to time t into two transitions, (a) the transition until they first meet at time s, and(b) the rest transition. The probability for the former transition is the first meeting probability ra,b:∗ (t). The probability
for the latter transition is the probability that the two random walkers starting from same node c0 ∈ V at time s meetagain at the same node c ∈ V at time t. Since node c0 and
node c can be any node, we denote such a probability byx∗0 ,∗0 :∗ (t − s). With these probabilities, xa,b:∗ (t) is

X d20 Xcs
c0 ∈V 2 c∈V

xc0 ,c0 :c (t),(22)

Pwhere s2 = i∈V di2 . The reason that x∗0 ,∗0 :∗ (t) is not set
as a simple sum of values of xc0 ,c0 :c (t) in Eq. (22) is as follows. According to Eq. (12), if t is sufficient large, the existing probability xa:i (t) is approximately proportional to theweighted degree di of node i. Therefore, the probability of
the first meeting of the two random walkers at node c0 canbe expected to be proportional to dc20 . Consequently, in thesum of Eq. (22), xc0 ,c0 :c (t) is weighted by dc20 /s2 . In Sect. 4,
the validity of Eq. (22) will be confirmed through numericalexamples.
The right-hand side of Eq. (21) is a convolutional sum,with the consequence that the generating function Xa,b:∗ (z)of xa,b:∗ (t) is
Xa,b:∗ (z) = Ra,b:∗0 (z) X∗0 ,∗0 :∗ (z).

(23)

From this equation, the generating function Ra,b:∗0 (z) of thefirst meeting probability ra,b:∗ isRa,b:∗0 (z) =

c∈V

c∈V

x∗0 ,∗0 :∗ (t) ≈Xa,b:∗ (z).
X∗0 ,∗0 :∗ (z)(24)

Substituting the spectral formulas of xa:i (t) and xb:i (t) given
by Eq. (11) into Eq. (16) yields the following spectral formula for Xa,b:∗ (z):Xa,b:∗ (z) =
=

X

√

c∈V

=

X
c∈V

√

∞
XX

xa:c (t) xb:c (t) zt

c∈V t=0n n
dc XX

qk (a)qk (c)qk0 (b)qk0 (c)∞X(λk λk0 z)t

da db k=1 k0 =1
t=0
n X
n
X
dc
qk (a) qk (c) qk0 (b) qk0 (c)da db k=1 k0 =1

1 − λk λk0 z

.

(25)

z takes a value within the range of |λk λk0 z| < 1 with theresult that the sum of the infinite geometric series converges.
From Eq. (22), the generating function X∗0 ,∗0 :∗ (z) isIEICE TRANS. COMMUN., VOL.E104–B, NO.6 JUNE 2021

608

X∗0 ,∗0 :∗ (z) ≈X d20 Xcs
c0 ∈V 2 c∈V

Xc0 ,c0 :c (z).

(26)

B(z) =

Substituting the generating function Ra,b:∗0 (z) into
Eq. (17) results in the expected first meeting time µa,b beingµa,b =∞
X
s=0s ra,b:∗0 (s) =Eq. (27). Similarly, B(z) is

dRa,b:∗0 (z)
.
dz
z=1

(27)

In this equation, dRa,b:∗0 (z)/dz is!
dRa,b:∗0 (z)d Xa,b:∗ (z)=dzdz X∗0 ,∗0 :∗ (z)dXa,b:∗ (z)dX∗0 ,∗0 :∗ (z)X∗0 ,∗0 :∗ (z) − Xa,b:∗ (z)dzdz=X∗20 ,∗0 :∗ (z)A(z) − B(z)
,
(28)
=
C(z)
where
dXa,b:∗ (z)X∗0 ,∗0 :∗ (z),dzdX∗0 ,∗0 :∗ (z),B(z) = Xa,b:∗ (z)dz
C(z) = X∗20 ,∗0 :∗ (z).
A(z) =(29)(35)

Substituting Eqs. (25) and (26) into the right-hand side ofEq. (30) yields B3 (z) and B2 (z) asX dc2q1 (a) q1 (c) q1 (b)
B3 (z)=
√
da db
c∈V


X X dc0 dc 2

2 0 

q1 (c) q1 (c ) ,(36)s2c∈V c0 ∈V




X X
dc qk (a) qk (c) qk0 (b) qk0 (c) 
B2 (z)=
√


1 − λk λk0 z
da dbc∈V 1≤k,k0 ≤n(k,k0 ),(1,1)
X X dc0 dc 2
20
q1 (c) q1 (c )
s2c∈V c0 ∈V




X
X

dc
1 
qk (a) qk (c) qk0 (b) qk0 (c)  .
= 2√1 − λk λk0 z
s1 c∈V da db1≤k,k0 ≤1(k,k0 ),(1,1)

(37)
(30)
(31)

According to Eqs. (25) and (26), A(z), B(z), and C(z) can be
written as polynomials for (1−z) because of 1−λ1 λ1 z = 1−z.
Hence, we also obtain A(z) as
A2 (z)A1 (z)A3 (z)++
A(z) =+ A0 (z).
(1 − z)3 (1 − z)2 1 − z

B3 (z)B2 (z)B1 (z)+++ B0 (z).
(1 − z)3 (1 − z)2 1 − z(32)

Substituting Eqs. (25) and (26) into the right-hand side ofEq. (29) yields A3 (z) and A2 (z) asX dc2q1 (a) q1 (c) q1 (b)
A3 (z)=
√
da db
c∈V


X X dc0 dc 2

2 0 

q1 (c) q1 (c ) ,(33)s2c∈V c0 ∈VX dc2A2 (z)=
q1 (a) q1 (c) q1 (b)
√
da db
c∈V




0
0
X
X
X

qk (c)qk (c )qk0 (c)qk0 (c ) dc0 dc




s2 1≤k,k0 ≤n
1 − λk λk0 zc∈V c0 ∈V(k,k0 ),(1,1)




X qk (c)qk (c0 )qk0 (c)qk0 (c0 ) 
1 X X
 .
= 2
dc0 dc
1 − λk λk0 z
s1 c∈V c0 ∈V1≤k,k0 ≤n(k,k0 ),(1,1)(34)
We do not provide A1 (z) and A0 (z) in this paper because
A1 (z)/(1 − z) and A0 (z) disappear when deriving µa,b using

Using these equations, we have found that A3 (z) = B3 (z).
Consequently, A(z) − B(z) in the numerator of Eq. (28) does
not contain the term (1 − z)−3 , with the result that the term
(1 − z)−2 becomes the highest-order term in the polynomialsfor (1 − z) in A(z) − B(z). Thus, C(z) isC(z) =

C1 (z)
C2 (z)++ C0 (z).
21−z(1 − z)(38)

Solving this equation in the same manner yields C2 (z) as2X X dc0 dc 2
q1 (c) q21 (c0 )
C2 (z) = s2c∈V c0 ∈V2
 1 X 2 (s2 )2=  2dc  = 4 .
(39)
s1 c∈Vs1
Since (A(z) − B(z))/C(z) is an indeterminate form at
z = 1, we discuss limz→1 (A(z) − B(z))/C(z) to derive thespectral formula of the expected first meeting time µa,b using
Eqs. (27) and (28). As the limit of z → 1, µa,b is(1 − z)2 (A(z)−B(z))A(z) − B(z)
= lim
z→1
z→1
C(z)
(1 − z)2 C(z)A2 (1) − B2 (1)=C2 (1)
2 
Xqk (c)qk (c0 )qk0 (c)qk0 (c0 )s1 X X

0 dc
=
d

c

1−λk λk0(s2 )2 c∈V c0 ∈V 1≤k,k0 ≤n(k,k0 ),(1,1)

X dc
X qk (a) qk (c) qk0 (b) qk0 (c) 

−
√

0
1−λ
λ
d
d
k
k
0
a
b
c∈V
1≤k,k ≤1

µa,b = lim(k,k0 ),(1,1)

SAKUMOTO and OHSAKI: GRAPH DEGREE HETEROGENEITY FACILITATES RANDOM WALKER MEETINGS

609"
1 X 2X 2dd0(s2 )2 c∈V c c0 ∈V c!#"nX
2qk (c)qk (c0 ) qk (c) qk (a) qk (b)
1
− √
s1
√
√ + √
1 − λkdc dc0dcdadb
k=2
X qk (c)qk0 (c) qk (c0 )qk0 (c0 ) qk (a)qk0 (b)!#
+s21
− √
.
(1−λk λk0 )dc
dc0
da db
1≤k,k0 ≤n=(k,k0 ),(1,1)(40)
Since this equation is expressed by the eigenvalues andeigenvectors of W, it is the spectral formula of µa,b .
Equation (40) appears to be complicated, but if we use
the expected first meeting time µa,b:c , the time until the two
random walkers first meet at node c ∈ V, then µa,b isµa,b =

where the spectral formula of µa,b:c isµa,b:c = µa:c + µb:c
X qk (c)qk0 (c) qk (c)qk0 (c) qk (a)qk0 (b)!
2
+s1
.
− √
(1−λk λk0 )dc
dc
da db
1≤k,k0 ≤nq̂kk0 t q̂kk0,
1 − λk λk0
1≤k,k0 ≤n
X

N̂† =

(46)

(k,k0 ),(1,1)(47)

Substituting N̂† into Eq. (40) yields the following as the expected first meeting time µa,b :ns21 X Xdc2 dc20 t ûcc N̂† (ûc0 c0 − ûab ).
s22 c∈V c0 =1µa,b =(48)

In this equation, ûab is(k,k0 ),(1,1)(42)
Note that Eq. (41) is derived by substituting Eq. (42) into
Eq. (40). Equation (42) can be obtained from the similar
derivation process of Eq. (40). Owing to space limitations,
we do not provide the detailed deviation process of Eq. (42)in this paper. In the derivation process of Eq. (42), we discuss the first meeting probability ra,b:c (t) of two random
walkers at node c ∈ V, and obtain µa,b:c as the expectation
with ra,b:c (t). As with the probability ra,b:∗ (t), the first meeting probability ra,b:c (t) is satisfied withûab := ua ⊗ ub ,(49)

where ua is the column vector whose ith element ua (i) is

1



if i = a √.
(50)ua (i) = d 0 a otherwise
The pseudo-inverse matrix N̂† of N̂ in Eq. (46) is alsoq̂kk0 t q̂kk0
1 − λk λk0
1≤k,k0 ≤nXN̂† =(k,k0 ),(1,1)

ra,b:c (s) xc,c:c (t − s).

(43)

s=0

Hence, the generating function Ra,b:c (z) for ra,b:c (t) is given
byXa,b:c (z)Ra,b:c (z) =.
Xc,c:c (z)(44)

Since µa,b:c = dRa,b:c (z)/dz|z=1 , we can derive the spectral
formula (42) of µa,b:c from Ra,b:c (z) like the spectral formula (40) of µa,b .
3.2

(45)

where I is the n × n unit matrix and ⊗ is the Kronecker product. According to the definition of the Kronecker product, Î
and Ŵ are n2 × n2 matrices. Let N̂† be the pseudo-inverse
matrix of N̂ with the result that N̂ N̂† N̂ = N̂,q̂kk0 := qk ⊗ qk0 .
(41)

xa,b:c (t) =N̂ := I ⊗ I − W ⊗ W = Î − Ŵ,

where q̂kk0 is the following column vector with n2 elements:

1 X 2X 2
1 X 2
dc µa,b:c − 2dcdc0 µc0 ,c0 :c ,s2 c∈Vs2 c∈V c0 ∈VtXexpected first meeting time µa,b on the basis of the clarified
principal component. We use the method for examining thefirst hitting time µa:i used in [14] to derive the principal component of µa,b .
First, we introduce

Principal Component of the Expected First Meeting
Time µa,b

We examine the principal component of µa,b with the spectral formula of the expected first meeting time µa,b and reveal mathematically the effect of the graph structure on the(1 − λk λk0 + λk λk0 ) q̂kk0 t q̂kk0
1 − λk λk0
1≤k,k0 ≤nX=(k,k0 ),(1,1)= Î − q̂11 t q̂11 + M̂,
where M̂ isM̂ =λk λk0 q̂kk0 t q̂kk0
1 − λk λk0
1≤k,k0 ≤nX(k,k0 ),(1,1)

=

X

∞ 
X
s
λk λk0 q̂kk0 t q̂kk0

1≤k,k0 ≤n s=1(k,k0 ),(1,1)


s


∞ 
X
 X

t


=
λk λk0 q̂kk0 q̂kk0 


s=1 
1≤k,k0 ≤n(k,k0 ),(1,1)(51)

IEICE TRANS. COMMUN., VOL.E104–B, NO.6 JUNE 2021

610

 n n
s
∞ X
X

 X

t
t
0
0
0
λk λk q̂kk q̂kk − q̂11 q̂11 
=

s=1

k=1 k0 =1

∞ 
X
s
=
Ŵ − q̂11 t q̂11
s=1
∞ 
s

2 X
Ŵ − q̂11 t q̂11
= Ŵ − q̂11t q̂11 + Ŵ − q̂11t q̂11s=0

q̂kk0 t q̂kk0. (52)
1−λk λk0
1≤k,k0 ≤n2 X= Ŵ − q̂11 t q̂11 + Ŵ − q̂11 t q̂11

(k,k0 ),(1,1)

This derivation process involved the use of(
1 if i = k and j = ltq̂i j q̂kl =,0 otherwise( q̂kk0 t q̂kk0 ) s = q̂kk0 t q̂kk0 .

(53)
(54)

Substituting Eq. (51) into Eq. (48) yields the following asµa,b :µa,b =ns21 s21 X X
d2 d20 t ûcc M̂(ûc0 c0 − ûab ).
+ 2
s2 s2 c∈V c0 =1 c c

The following was used to obtain this equation:tûcc N̂† (ûc0 c0 − ûab )hi= t ûcc Î − q̂11 t q̂11 + M̂ (ûc0 c0 − ûab )

1 t



 2 + ûcc M̂(ûc0 c0 − ûab ) if c = c0
.
=
dc


 t û M̂(û 0 0 − û )otherwise
cc

cc

(57)
The right-hand side of this equation expresses the error between µa,b and the principal component s21 /s2 .
We examine the upper bound on the right-hand side ofEq. (57) usingûcc M̂(ûc0 c0 − ûab )= t ûcc Ŵ − q̂11 t q̂11 (ûc0 c0 − ûab )
2 X q̂kk0 t q̂kk0+ t ûcc Ŵ − q̂11 t q̂11
(ûc0 c0 − ûab )1−λk λk0
1≤k,k0 ≤n(k,k0 ),(1,1)

ûi jŴ ûkl = t uiWuk ⊗ t u jWul
w jl
w2
wik
⊗
≤ max
,
4
di dk d j dl
dmin



2
Ŵ ûi j = t Ŵ ûi j Ŵ ûi j
=

(56)

n
µa,b
1 XX 2 2 t
1=−
dc dc0 ûcc M̂(ûc0 c0 − ûab ) .
s2
s21
s22 c∈V c0 =1

t

t

=

The first term on the right-hand side of Eq. (55) corresponds
to the principal component of the expected first meeting time
µa,b .
To confirm that s21 /s2 is the principal component of the
expected first meeting time µa,b , we discuss

for 2 ≤ k, k0 ≤ n. Using the above equation, we obtain

The following was used in this derivation process:

(55)

ab

1
1
≤
,
1 − λk λk0
1 − λ2≤ t ûcc Ŵ − q̂11 t q̂11 (ûc0 c0 − ûab )
2

1 t 
+
ûcc Ŵ − q̂11 t q̂11 Î− q̂11 t q̂11 (ûc0 c0 − ûab )
1−λ2
1 t
t
ûccŴ 2 (ûc0 c0 − ûab )= ûccŴ(ûc0 c0 − ûab ) +1−λ2
1= t ûccŴ(ûc0 c0 − ûab ) +Ŵ ûcc Ŵ(ûc0 c0 − ûab )
1−λ2
√
2 w2
1 wmax 2 wmax
≤ 4max +221−λ2 dmin
dmin
dmin
!
2 w2
1
≤ 4max+1 .
(59)
dmin 1−λ2

(58)

n X
n
X

w2ki w2l jk∈∂i l∈∂ jdk di2 dl d2j≤nn
w2max X X
wki wl j2
di2 d2j dmink∈∂i l∈∂ j

=

w2max
w2max
≤
.
2
4
di d j dmin
dmin

(60)

(61)

Substituting Eq. (59) into Eq. (57) yields the following
as the upper bound of the error between µa,b and the principal component s21 /s2 :!
2 w2max
µa,b
1
1
−
≤ 4
+1 .
(62)
s2
s21
dmin 1 − λ2
According to this equation, the error can be expected to besmall for graph G, where λ2 and wmax are small but dmin islarge. In this case, the expected first meeting time µa,b isapproximated asµa,b ≈

s21
n
,
=
2
2
s2 1 + dstd
/davg

(63)

where davg and dstd are the average and standard deviationof weighted degrees, respectively. Equations (62) and (63)are coincidentally similar to Eqs. (14) and (15), respectively.
Since the analysis target for Eqs. (62) and (63) is different
from that of Eqs. (14) and (15), these equations are new
findings. In Sect. 4, we will show that the right hand sideof Eq. (62) is not large enough to be a problem in popular random graphs (Barabási-Albert graphs and Erdös-Rényigraphs). In this paper, the graphs where the right-hand sideof Eq. (62) is negligibly small are not yet clear. However,since Eq. (14) based on the result of [14] and Eq. (62) are coincidentally similar, we may prove that the right hand side of

SAKUMOTO and OHSAKI: GRAPH DEGREE HETEROGENEITY FACILITATES RANDOM WALKER MEETINGS

611

Eq. (62) is negligibly small in several graphs (e.g., -graphs,
k-nearest neighbor graphs, Gaussian similarity graphs, andErdös-Rényi graphs) on the basis of the similar discussionin [14].
If the approximation formula (63) holds for the expected first meeting time µa,b , we derive the following characteristics: (a) µa,b is small when the coefficient of variation
dstd /davg is large and (b) µa,b does not depend on the starting
nodes a and b. Characteristic (a) is useful for understanding the effect of the graph structure on µa,b . The reason why
characteristic (b) emerges can be explained as follows. First,
a random walk is a Markov chain, and thus the informationof the initial state is lost over time. Since the time to lose
the information is shorter than the first meeting time of two
random walks, the expected first meeting time would be independent of the starting nodes. As the number of nodes
in a graph increases, the first meeting time becomes longer.
Hence, in order for the independency of the expected firstmeeting time to emerge, the graph should be large enough.
4.

Numerical Example

In this section, we confirm the validity of the spectral formula (40) and the principal component of the expected firstmeeting time µa,b revealed in Sect. 3. We also examine theerror in the approximation formula (63) obtained when µa,b
is replaced by its principal component.
4.1

Setting

In this subsection, we use BA (Barabási-Albert) graphs [15]and ER (Erdös-Rényi) graphs [16]. The spectral formula (40) and the approximation formula (63) depend on the
degree distribution of a graph. Since the degree distributionof a BA graph is different from that of an ER graph, thesegraphs are useful for clarifying the effects of the degree distribution on these formulas. Owing to space limitations, we
provide the results for unweighted graphs, where wi j = 1
is provided for all links ∀(i, j) ∈ E. In unweighted graphs,
the weighted degree di of node i corresponds to the degree
mi , the number of links of node i. According to the spectral
characteristics of ER graphs and BA graphs shown in [17],our analysis results may be valid in these graphs. Hence, thescope of the numerical example seems to be biased. However, these graphs are popular random graphs, and thus thisnumerical example is worthwhile as the first step to confirm
the validity of our analysis results.
The BA model [15] is a typical model for scale-free
random graphs. A BA graph is generated using the following procedure. First, a complete graph with n0 nodes
is created. We assume that n0 = m for the sake of simplicity. Next, nodes are inserted one by one until the numberof nodes in the BA graph is equal to n. When adding thetth node (t = m + 1, m + 2, · · · , n), mnew links are createdfrom node t to nodes j ∈ {1, 2, · · · , t − 1} with the connecBAtion probability pBA
j (t). The connection probability p j (t)ism j (t)pBA,j (t) = Pt−1
l=1 ml (t)(64)

where m j (t) is the degree of node j when the insertion of thet − 1th node is completed. BA graphs have the power-law
degree distribution (i.e, Prob [mi = m] ∼ m−3 ). If G is unweighted, then the average weighted degree davg is equal tothe average degree kavg . Hence, the average weighted degree
davg of a BA graph is approximated as
davg =m (m − 1) + 2 m (n − m)
≈ 2 m,
n(65)

where we assume that n  m.
In contrast, the ER model [16] is a classical randomgraph model. An ER graph is generated through the following procedure. First, n nodes are created. Next, links are
created between any pair of nodes with probability pER . If
the graph is not connected, then the link creation process isbegun again. The average weighted degree davg of an ER
graph isdavg = (n − 1) pER .

(66)

The degree distribution Prob [mi = m] of an ER graph follows the binomial distribution. According to the difference
between the power law and the binomial distribution, thestandard deviation dstd of weighted degrees in a BA graph isgreater than that in an ER graph.
To focus on the difference in the standard deviation dstd
of weighted degrees, we set m and pER as
$
%
davg
m=
,
(67)
2
davg
pER =
,
(68)
n−1
with the result that the average weighted degree davg of an
ER graph and a BA graph are roughly equal. The minimum
weighted degree dmin in both graphs also increases as davg
increases.
To examine the validity and the error of the spectral formula (40) and the approximation formula (63), we measure
the average of the first meeting times in simulation using thefollowing procedure.
1. Generate a BA graph or an ER graph using the above
procedures.
2. Put random walkers on nodes a ∈ V and b ∈ V.
3. Move each random walker with the transition probability pi→ j in accordance with Eq. (2).
4. Repeat step 3 until the two random walks meet at thesame node.
5. Repeat step 2 through step 4 10,000 times to calculate
the average of the first meeting times.
We use the parameter configuration shown in Table 1 as adefault parameter configuration.

IEICE TRANS. COMMUN., VOL.E104–B, NO.6 JUNE 2021

612
Table 1

Parameter configuration.

Number of nodes
Weight of link (i, j)
Average weighted degree
Random walker’s starting node

n
wi j
davg
a

1,000
1
6
1

Fig. 4 Average weighted degree davg vs. the average and the maximumof the relative error a,b for the expected first meeting µa,b .

a,b :=
Fig. 2 Expected first meeting time µa,b for different settings of the starting node b of the random walker in BA graphs.

Fig. 3 Expected first meeting time µa,b for different settings of the starting node b of the random walker in ER graphs.

4.2

Validity of the Spectral Formula for the Expected First
Meeting Time µa,b

We confirm the validity of the spectral formula of the expected first meeting time µa,b given by Eq. (40).
Figures 2 and 3 show the first meeting times obtained
from the simulation and the analysis (i.e., the spectral formula (40)) for different settings of the random walker’s starting node b in the BA and ER graphs, respectively. According to Figs. 2 and 3, the analysis results are almost the sameas the simulation results regardless of the choice of n and b.
We then evaluate the error in the spectral formula (40).
In this evaluation, we use the relative error a,b of the expected first meeting time µa,b . The relative error a,b is defined asµa,b − µsim
a,b
µsim
a,b

,

(69)

where µsim
a,b is the average of the first meeting times obtained
from the simulation. We examine the average and the maximum of the relative errors a,b when changing starting nodeb while the starting node a is fixed.
Figure 4 shows the average and the maximum of therelative errors a,b of the expected first meeting time µa,b in
the BA and ER graphs with different settings of the average weighted degree davg . In this figure, we do not plot theresults for the ER graphs with davg = 2 and 4, because a connected ER graph cannot be generated. According to Fig. 4,
if davg ≥ 4, then the maximum of relative errors a,b is only
a few percent. Therefore, the spectral formula (40) is valid
for the graphs with davg ≥ 4.
We discuss the reason that the relative error a,b is large
when we use a BA graph with a small-average weighted degree (i.e., davg = 2). In Sect. 3, we use Eq. (22) to derive thespectral formula (40). Equation (22) assumes that the firstmeeting probability of two random walkers at node c is proportional to dc2 . Hence, we confirm the acceptance of thisassumption to clarify the reason for the large relative error.
Figures 5(a) through (c) show scatter plots of the firstmeeting frequency of two random walkers at node c in BA
graphs with different settings of the average weighted degree davg . The first meeting frequency at each node was obtained from the simulation, where the starting nodes a andb are fixed. In order to confirm easily the correctness of
the assumption, we plot the fitting curve of dc2 in these figures. According to Figs. 5(a) through (c), the first meeting
frequencies with davg = 2 differ only largely from the fitting
curve, with the consequence that the assumption must not
be accepted for the cases with davg = 2. Therefore, we conclude that the large relative error shown in Fig. 4 is causedby the assumption for Eq. (22).
According to the results, the spectral formula of firstmeeting time µa,b will be valid if the average weighted degree davg is sufficiently large (i.e., davg ≥ 4).

SAKUMOTO and OHSAKI: GRAPH DEGREE HETEROGENEITY FACILITATES RANDOM WALKER MEETINGS

613

Fig. 5

4.3

Weighted degree dc of node c vs. the first meeting frequency at node c in BA graphs.

Validity for the Principal Component of the Expected
First Meeting Time µa,b

We clarify the validity for the principal component of the
expected first meeting time µa,b derived in Sect. 3. Specifi0
cally, we examine the relative error a,bof the approximation
formula (63) obtained when the expected first meeting time
µa,b is given by the principal component (i.e., s21 /s2 ). The
0relative error a,b
is defined as
0
a,b
:=

s21
sim
s2 − µa,b

µsim
a,b

.

(70)

Figures 6 and 7 show the averages of the relative er0
rors a,bof the approximation formula (63) for BA and ER
graphs with different numbers of nodes, n, respectively. The
0average of the relative errors a,b
was calculated from 10,000
simulations, where the starting nodes a and b are selected
randomly. In Fig. 7, we do not plot the result for n = 10, 000
and davg = 6, because a connected ER graph cannot be generated. According to the results, if the average weighted de0
gree davg is sufficiently large, the relative error a,b
is small,and the derived principal component is valid. This can also
be explained by Eq. (62). The right-hand side of Eq. (62)represents the upper bound of the error in the approximation
formula (63). If the average weighted degree davg is large,
the minimum weighted degree dmin is also large. As theminimum weighted degree dmin increases, the upper bound0of the approximabecomes small, and the relative error a,btion formula (63) can be expected to decrease. Moreover,according to Figs. 6 and 7, the average of the relative errors
0a,bis constant or becomes smaller as n increases, and hence
the approximation formula (63) is also effective for largescale graphs.
From the above results, the derived principal component is valid if the average weighted degree davg is sufficiently large (i.e., davg ≥ 4). According to the site [18],which collecting statistical information (e.g., average degree) of various existing graphs, the average degree of a typical graph is greater than four. Hence, our analysis results
are expected to be useful for many real graphs.
Finally, we confirm the effect of the graph structure on
the expected first meeting time µa,b revealed in Sect. 3. Ac-

0 ofFig. 6 Number of nodes, n, vs. the average of the relative errors a,b
the approximation formula (63) in the BA graphs.

0 ofFig. 7 Number of nodes, n, vs. the average of the relative errors a,b
the approximation formula (63) in the ER graphs.

cording to the approximation formula (63), µa,b increases
as s21 /s2 increases. To confirm the effect from the numerical example, we compare s21 /s2 and the average of the firstmeeting times obtained in the simulation.
Figures 8 and 9 show the averages of the first meetingtimes obtained from the simulation with different settings of
s21 /s2 in the BA and ER graphs, respectively. To calculate
the average of the first meeting times, we conduct 10,000
simulations, where the starting nodes a and b are selected
randomly. In these figures, we plot the straight line for y = x
to confirm the effect easily. According to the results, theIEICE TRANS. COMMUN., VOL.E104–B, NO.6 JUNE 2021

614

fects of the graph structures, the variance of the coefficientfor weighted degrees, dstd /davg (degree heterogeneity), facilitates the meeting of random walkers.
As future work, we plan to examine the validity of theanalysis results with real graphs and apply them to the development of efficient graph algorithms.
Acknowledgments
This work was supported by JSPS KAKENHI Grant Number 19K11927.
References
Fig. 8 Principal component s21 /s2 vs. the average of the first meetingtimes in the BA graphs.

Fig. 9 Principal component s21 /s2 vs. the average of the first meetingtimes in the ER graphs.

average of the first meeting times is approximately along
the y = x line, except for the result for BA graphs withaverage weighted degree davg = 2. Therefore, the effect isalso confirmed from the numerical example if the average
weighted degree davg is sufficiently large.
5.

Conclusion and Future WorkIn this paper, we analyzed the first meeting time of multiple random walks in arbitrary graphs and clarified the effects of graph structures on its expected value. First, wederived the spectral formula of the expected first meetingtime for two random walkers using spectral graph theory.
Then, we examined the principal component of the expected
first meeting time using the derived spectral formula. The
clarified principal component reveals that (a) the expected22first meeting time is almost dominated by n/(1 + dstd
/davg),
and (b) the expected first meeting time is independent of thestarting nodes of random walkers, where n is the number ofnodes. davg and dstd are the average and the standard deviation of the weighted degree, respectively. Characteristic (a)is useful for understanding the effect of the graph structureon the first meeting time. In addition, we confirmed the validity of the analysis results through numerical examples using popular random graphs. According to the revealed ef-[1] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, “Search and replication in unstructured peer-to-peer networks,” Proc. 16th ACM international conference on Supercomputing (ICS’02), pp.84–95, June
2002.
[2] C. Gkantsidis, M. Mihail, and A. Saberi, “Random walks in peer-topeer networks,” Proc. 23rd Conference of the IEEE Communications
Society (INFOCOM 2004), pp.120–130, March 2004.
[3] C. Dutta, G. Pandurangan, R. Rajaraman, and S. Roche,“Coalescing-branching random walks on graphs,” ACM Trans. Parallel Comput. (TOPC), vol.2, no.3, pp.1–29, Nov. 2015.
[4] Y. Metivier, N. Saheb, and A. Zemmari, “Randomized rendezvous,”
Mathematics and Computer Science, pp.183–194, Birkhäuser,
Basel, 2000.
[5] A. Israeli and M. Jalfon, “Token management schemes and random walks yield self-stabilizing mutual exclusion,” Proc. 9th Annual ACM Symposium on Principles of Distributed Computing(PODC’90), pp.119–131, ACM, Aug. 1990.
[6] P. Tetali and P. Winkler, “On a random walk problem arising in
self-stabilizing token management,” Proc. 10th annual ACM symposium on Principles of distributed computing (PODC’91), pp.273–
280, ACM, Aug. 1991.
[7] D. Coppersmith, P. Doyle, P. Raghavan, and M. Snir, “Random
walks on weighted graphs and applications to on-line algorithms,”
J. ACM, vol.40, no.3, pp.421–453, July 1993.
[8] D.J. Aldous, “Meeting times for independent Markov chains,”
Stochastic Processes and their Applications, vol.38, no.2, pp.185–
193, Aug. 1991.
[9] N.H. Bshouty, L. Higham, and J. Warpechowska-Gruca, “Meetingtimes of random walks on graphs,” Inform. Process. Lett., vol.69,
no.5, pp.259–265, 1999.
[10] C. Cooper, A. Frieze, and T. Radzik, “Multiple random walks in
random regular graphs,” SIAM J. Discrete Math., vol.23, no.4,
pp.1738–1761, June 2009.
[11] Y. Zhang, Z. Tan, and B. Krishnamachari, “On the meetingtime for two random walks on a regular graph,” arXiv preprint
arXiv:1408.2005, 2014.
[12] M. George, R. Patel, and F. Bullo, “The meeting time of multiple
random walks,” Preprint submitted to Linear Algebra and Its Applications, March 2017, available at http://motion.me.ucsb.edu/pdf/
2014l-gpb.pdf[13] L. Lovász, “Random walks on graphs: A survey,” Combinatorics,
Paul Erdős is eighty, vol.2, pp.353–398, 1996.
[14] U. Von Luxburg, A. Radl, and M. Hein, “Hitting and commutetimes in large random neighborhood graphs,” The Journal of Machine Learning Research, vol.15, no.1, pp.1751–1798, Jan. 2014.
[15] A.L. Bárabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol.286, no.5439, pp.509–512, Oct. 1999.
[16] P. Erdös and A. Rényi, “On random graphs,” Mathematicae, vol.6,
no.26, pp.290–297, 1959.
[17] Y. Sakumoto and M. Aida, “Wigner’s semicircle law of weighted
random networks,” IEICE Trans. Commun., vol.E104-B, no.3,

SAKUMOTO and OHSAKI: GRAPH DEGREE HETEROGENEITY FACILITATES RANDOM WALKER MEETINGS

615

pp.251–261, March 2021.
[18] J. Kunegis, “The Koblenz network collection (KONECT),” http://konect.uni-koblenz.de/ (accessed on May 29, 2020).

Yusuke Sakumotoreceived M.E. and Ph.D.
degrees in the Information and Computer Sciences from Osaka University in 2008 and 2010,
respectively. From 2010 to 2019, he was a associate professor of Tokyo Metropolitan University. He is currently an associate professor at
Kwansei Gakuin University. His research work
is in the area of analysis of communication network and social network. He is a member of theIEEE, IEICE and IPSJ.

Hiroyuki Ohsaki
received the M.E. degree in the Information and Computer Sciencesfrom Osaka University, Osaka, Japan, in 1995.
He also received the Ph.D. degree from Osaka
University, Osaka, Japan, in 1997. He is currently a professor at Department of Informatics, School of Science and Technology, Kwansei Gakuin University, Japan. His research work
is in the area of design, modeling, and controlof large-scale communication networks. He isa member of IEEE and Institute of Electronics,
Information, and Computer Engineers of Japan (IEICE).