Randomized Rumour Spreading: The Effect of the Network Topology
Randomized Rumour Spreading: The Effect of the Network Topology
复制标题
随机谣言传播：网络拓扑的影响
DOI：
10.1017/s0963548314000194
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
H. Sun
中科院分区：
文献类型：
--
作者：
K. Panagiotou;X. Perez-Gimenez;T. Sauerwald;H. Sun
我们考虑流行的和研究得很好的推模型，这是用来传播信息在一个给定的网络与n个顶点。最初，某个顶点拥有一个谣言，并将其传递给随机选择的一个邻居。在随后的每一轮中，每个知道谣言的顶点都会通知随机邻居。它已被证明在各种网络拓扑结构，该算法成功地在O（log n）轮内传播谣言。然而，许多研究是相当粗糙的，涉及巨大的常数，不允许不同的网络拓扑结构之间的直接比较。在本文中，我们分析了几个重要的图族上的推模型，并得到了严格的运行时间估计。我们首先表明，对于任何几乎正则图的n个顶点与小的谱扩展，谣言传播后完成log 2n + log n+o（log n）轮的概率很高。这是第一个结果，展示了一个一般的图形类，其中谣言传播基本上是一样快的完全图。此外，对于随机图G（n，p），p= clog n/n，其中c > 1，我们以高概率确定谣言传播的运行时间为log 2n + γ（c）log n，其中γ（c）= clog（c/（c−1））.特别地，这表明我们的第一个结果中几乎正则性的假设是必要的。最后，对于n=2d顶点上的超立方体，运行时间具有高概率至少为（1+β）<$（log 2n + log n），其中β > 0。这表明超立方体上的推模型比完全图上的推模型慢，从而表明我们第一个结果中的小谱展开假设也是必要的。此外，我们的结果结合超立方体的O（log n）上限（参见[11]）意味着推模型在超立方体上比在随机图G（n，clog n/n）上更快，其中c足够接近1。
We consider the popular and well-studied push model, which is used to spread information in a given network with n vertices. Initially, some vertex owns a rumour and passes it to one of its neighbours, which is chosen randomly. In each of the succeeding rounds, every vertex that knows the rumour informs a random neighbour. It has been shown on various network topologies that this algorithm succeeds in spreading the rumour within O(log n) rounds. However, many studies are quite coarse and involve huge constants that do not allow for a direct comparison between different network topologies. In this paper, we analyse the push model on several important families of graphs, and obtain tight runtime estimates. We first show that, for any almost-regular graph on n vertices with small spectral expansion, rumour spreading completes after log2n + log n+o(log n) rounds with high probability. This is the first result that exhibits a general graph class for which rumour spreading is essentially as fast as on complete graphs. Moreover, for the random graph G(n,p) with p=c log n/n, where c > 1, we determine the runtime of rumour spreading to be log2n + γ (c)log n with high probability, where γ(c) = clog(c/(c−1)). In particular, this shows that the assumption of almost regularity in our first result is necessary. Finally, for a hypercube on n=2d vertices, the runtime is with high probability at least (1+β) ⋅ (log2n + log n), where β > 0. This reveals that the push model on hypercubes is slower than on complete graphs, and thus shows that the assumption of small spectral expansion in our first result is also necessary. In addition, our results combined with the upper bound of O(log n) for the hypercube (see [11]) imply that the push model is faster on hypercubes than on a random graph G(n, clog n/n), where c is sufficiently close to 1.
登录
查看更多内容
更多集合、图表和数字
DOI：
10.1007/978-3-540-32439-3
发表时间：
2006
期刊：
ArXiv
影响因子：
--
作者：
E. Győri;G. Katona;L. Lovász;T. Fleiner
通讯作者：
T. Fleiner
影响因子：
1
作者：
Colin Cooper;A. Frieze
通讯作者：
Colin Cooper;A. Frieze
A·哈贝：（1989）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--
随机网络中的可靠广播和密度的影响
DOI：
--
发表时间：
2010
期刊：
2010 Proceedings IEEE INFOCOM
影响因子：
--
作者：
N. Fountoulakis;Anna Huber;K. Panagiotou
通讯作者：
K. Panagiotou
封面时间和播出时间
DOI：
10.4230/lipics.stacs.2009.1842
发表时间：
2009
期刊：
ArXiv
影响因子：
--
作者：
Robert Elsässer;Thomas Sauerwald
通讯作者：
Thomas Sauerwald