Coalescing Random Walks and Voting on Connected Graphs
Coalescing Random Walks and Voting on Connected Graphs
复制标题
DOI：
10.1137/120900368
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
C. Cooper;Robert Elsässer;H. Ono;T. Radzik
中科院分区：
文献类型：
--
作者：
C. Cooper;Robert Elsässer;H. Ono;T. Radzik
在合并随机游走中，一组粒子在图上进行独立的随机游走。当一个或多个粒子在一个顶点相遇时，它们会合并成一个粒子，然后继续在图中随机游走。聚合随机游动可以用来在分布式网络中实现共识，是Israeli和Jalfon的自稳定互斥算法的基础。设G=（V，E），是一个无向连通的n点m边图.设C（n）是所有粒子聚结的期望时间，当最初一个粒子位于n顶点图的每个顶点时。本文研究了一般图类的聚并时间C（n）的界问题。我们的主要结果是C（n）= O（1/（1-d^da_2））*（（log n）^4 +n/A）），其中d^da_2是随机游动的转移矩阵的第二大特征值的绝对值，A=（sum d^2（v））/（d^2 n），d（v）是顶点v的度，d是节点的平均度.参数A是节点度的可变性的指示符。因此1 <= A =O（n），其中A=1。
In a coalescing random walk, a set of particles make independent random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon. Let G=(V,E), be an undirected, connected n vertex graph with m edges. Let C(n) be the expected time for all particles to coalesce, when initially one particle is located at each vertex of an n vertex graph. We study the problem of bounding the coalescence time C(n) for general classes of graphs. Our main result is that C(n)= O(1/(1-lambda_2))*((log n)^4 +n/A)), where lambda_2 is the absolute value of the second largest eigenvalue of the transition matrix of the random walk, A= (sum d^2(v))/(d^2 n), d(v) is the degree of vertex v, and d is the average node degree. The parameter A is an indicator of the variability of node degrees. Thus 1 <= A =O(n), with A=1 for regular graphs.