Local Mixing Time: Distributed Computation and Applications
Local Mixing Time: Distributed Computation and Applications
复制标题
局部混合时间：分布式计算和应用
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Gopal Pandurangan
中科院分区：
文献类型：
--
作者：
A. R. Molla;Gopal Pandurangan
图的混合时间是一个重要的度量，它不仅可以用来分析网络的连通性和扩张性，而且也是设计高效算法的关键参数。我们引入了一个新的概念，混合的随机游动（无向）图，称为本地混合。非正式地，相对于一个给定的节点s的局部混合，是一个随机游走概率分布的混合限制到一个足够大的节点子集-说，一个子集的大小至少n/？对于给定的参数？- 包含S。通过从源节点s开始的随机游走在这样的子集上混合的时间被称为相对于s的局部混合时间。本地混合时间捕获的本地连接和扩展属性围绕一个给定的源节点，是一个有用的参数，确定部分信息传播，八卦等算法的运行时间。我们的第一个贡献是正式定义的概念，在无向图的本地混合时间。然后，我们提出了一个有效的分布式算法，计算一个常数因子近似的局部混合时间相对于一个源节点s的在？s）圆^1在哪里？_ s是n结点正则图中的局部混合时间w.r.t s。这个约束什么时候成立？s明显小于局部混合组的电导（即，行走局部混合的集合）;这通常是局部混合时间显著小于混合时间（相对于s）的有趣情况。我们还提出了一个分布式算法，计算精确的本地混合时间在dk（？_ s D）轮，其中D =min{？_ s，D}，D是图的直径（这个界无条件成立，没有任何假设？s）。我们的算法工作在分布式计算的CONGEST模型。由于局部混合时间在许多图中可以显著小于混合时间（甚至直径），因此它在某些算法应用中用作分布式复杂度的更严格度量。特别是，我们表明，当地的混合时间紧密的部分信息传播的复杂性，这反过来又是有用的，在解决其他问题，如最大覆盖问题，充分的信息传播，领导选举等。
The mixing time of a graph is an important metric, which is not only useful in analyzing connectivity and expansion properties of the network, but also serves as a key parameter in designing efficient algorithms. We introduce a new notion of mixing of a random walk on a (undirected) graph, called local mixing. Informally, the local mixing with respect to a given node s, is the mixing of a random walk probability distribution restricted to a large enough subset of nodes – say, a subset of size at least n/? for a given parameter ? – containing s. The time to mix over such a subset by a random walk starting from a source node s is called the local mixing time with respect to s. The local mixing time captures the local connectivity and expansion properties around a given source node and is a useful parameter that determines the running time of algorithms for partial information spreading, gossip etc. Our first contribution is formally defining the notion of local mixing time in an undirected graph. We then present an efficient distributed algorithm which computes a constant factor approximation tthe local mixing time with respect to a source node s in Õ(?_s) rounds^1 where ?_s is the local mixing time w.r.t s in an n-node regular graph. This bound holds when ?_s is significantly smaller than the conductance of the local mixing set (i.e., the set where the walk mixes locally); this is typically the interesting case where the local mixing time is significantly smaller than the mixing time (with respect to s). We also present a distributed algorithm that computes the exact local mixing time in Õ(?_s D) rounds, where D =min{?_s, D} and D is the diameter of the graph (this bound holds unconditionally without any assumptions on ?_s). Our algorithms work in the CONGEST model of distributed computing. Since the local mixing time can be significantly smaller than the mixing time (or even the diameter) in many graphs, it serves as a tighter measure of distributed complexity in certain algorithmic applications. In particular, we show that local mixing time tightly characterizes the complexity of partial information spreading which in turn is useful in solving other problems such as the maximum coverage problem, full information spreading, leader election etc.