论文标题
图学度异质性促进随机沃克会议
Graph Degree Heterogeneity Facilitates Random Walker Meetings
论文作者
论文摘要
已经开发了多个随机步行，这是多个图形的各种图形算法，这是图形上几个独立的随机步行者的运动。根据多个随机步行设计有效的图形算法需要从理论上研究多个随机步行，以深入了解其特征。第一个会议时间是多次随机步行的重要指标之一。图表上的第一个会议时间是由多个随机步行者在图中相同节点相交的时间定义的。这次与Rendezvous问题密切相关，这是计算机科学中的基本问题。之前已经分析了多次随机步行的第一个会议时间，但是其中许多分析集中在常规图上。在本文中，我们在任意图中分析了多次随机步行的第一个会议时间，并阐明了图结构对预期值的影响。首先，我们根据光谱图理论得出了预期的第一会议时间的光谱公式。然后，我们使用派生的光谱公式检查了预期的首次会议时间的主要成分。澄清的主体组件表明，（a）预期的第一次会议时间几乎由$ n/（1+d _ {\ rm std}^2/d _ {\ rm avg}^2）$和（b）预期的第一个会议时间独立于随机步行者的起始节点，而$ n $ n $ n $ n of node n of Nodes nodes of Nodes of Nodes of Nodes of Nodes of Nodes of nodes of nodes of nodes of nodes of nodes of nodes of nodes of nodes of nodes of nodes of nodes of nodes。 $ d _ {\ rm avg} $和$ d _ {\ rm std} $分别是加权节点学位的平均值和标准偏差。特征（a）对于理解图形结构对第一个会议时间的影响很有用。根据图形结构的揭示效果，系数$ d _ {\ rm std}/d _ {\ rm avg} $（度异质性）的差异促进了随机步行者的会议。
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.
