Tight Bounds for Rumor Spreading with Vertex Expansion
Tight Bounds for Rumor Spreading with Vertex Expansion
复制标题
通过顶点扩展限制谣言传播
DOI：
10.1137/1.9781611973402.59
复制
发表时间：
2013
影响因子：
2.5
通讯作者：
George Giakkoupis
中科院分区：
文献类型：
--
作者：
George Giakkoupis
我们建立了一个边界的经典PUSH-PINGS谣言传播协议的一般图，在图的顶点扩展。我们证明了O（log 2（n）/α）轮足以以高概率将谣言从任何单个节点传播到所有n个节点，在任何顶点扩展至少为α的图中。这个界限匹配一个已知的下限，并解决了Chierichetti，Lattanzi和Panconesi（SODA 2010）提出的关于谣言传播和顶点扩张之间关系的自然问题。此外，证明中使用的一些论点可能是独立的兴趣，因为它们提供了新的见解，例如，如何选择一小部分节点来最初植入谣言，以保证谣言快速传播。
We establish a bound for the classic PUSH-PULL rumor spreading protocol on general graphs, in terms of the vertex expansion of the graph. We show that O(log2(n)/α) rounds suffice with high probability to spread a rumor from any single node to all n nodes, in any graph with vertex expansion at least α. This bound matches a known lower bound, and settles the natural question on the relationship between rumor spreading and vertex expansion asked by Chierichetti, Lattanzi, and Panconesi (SODA 2010). Further, some of the arguments used in the proof may be of independent interest, as they give new insights, for example, on how to choose a small set of nodes in which to plant the rumor initially, to guarantee fast rumor spreading.