The search functionality is under construction.

The search functionality is under construction.

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 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_{
m std}^2/d_{
mavg}^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*_{avg} and *d*_{std} are the average and the standard deviation of weighted node degrees, respectively. 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*_{std}/*d*_{avg} (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.

- Publication
- IEICE TRANSACTIONS on Communications Vol.E104-B No.6 pp.604-615

- Publication Date
- 2021/06/01

- Publicized
- 2020/12/14

- Online ISSN
- 1745-1345

- DOI
- 10.1587/transcom.2020EBP3093

- Type of Manuscript
- PAPER

- Category
- Fundamental Theories for Communications

Yusuke SAKUMOTO

Kwansei Gakuin University

Hiroyuki OHSAKI

Kwansei Gakuin University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yusuke SAKUMOTO, Hiroyuki OHSAKI, "Graph Degree Heterogeneity Facilitates Random Walker Meetings" in IEICE TRANSACTIONS on Communications,
vol. E104-B, no. 6, pp. 604-615, June 2021, doi: 10.1587/transcom.2020EBP3093.

Abstract: 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 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_{
m std}^2/d_{
mavg}^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*_{avg} and *d*_{std} are the average and the standard deviation of weighted node degrees, respectively. 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*_{std}/*d*_{avg} (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.

URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2020EBP3093/_p

Copy

@ARTICLE{e104-b_6_604,

author={Yusuke SAKUMOTO, Hiroyuki OHSAKI, },

journal={IEICE TRANSACTIONS on Communications},

title={Graph Degree Heterogeneity Facilitates Random Walker Meetings},

year={2021},

volume={E104-B},

number={6},

pages={604-615},

abstract={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 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_{
m std}^2/d_{
mavg}^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*_{avg} and *d*_{std} are the average and the standard deviation of weighted node degrees, respectively. 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*_{std}/*d*_{avg} (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.},

keywords={},

doi={10.1587/transcom.2020EBP3093},

ISSN={1745-1345},

month={June},}

Copy

TY - JOUR

TI - Graph Degree Heterogeneity Facilitates Random Walker Meetings

T2 - IEICE TRANSACTIONS on Communications

SP - 604

EP - 615

AU - Yusuke SAKUMOTO

AU - Hiroyuki OHSAKI

PY - 2021

DO - 10.1587/transcom.2020EBP3093

JO - IEICE TRANSACTIONS on Communications

SN - 1745-1345

VL - E104-B

IS - 6

JA - IEICE TRANSACTIONS on Communications

Y1 - June 2021

AB - 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 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_{
m std}^2/d_{
mavg}^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*_{avg} and *d*_{std} are the average and the standard deviation of weighted node degrees, respectively. 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*_{std}/*d*_{avg} (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.

ER -