Rumour spreading and graph conductance

Rumour spreading and graph conductance
复制标题

谣言传播和图表电导

DOI：
--
复制
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
通讯作者：
A. Panconesi
A. Panconesi
中科院分区：
--
文献类型：
--
作者：
Flavio Chierichetti;Silvio Lattanzi;A. Panconesi

文献摘要

被引文献

相似文献

我们证明，如果具有 n 个节点的连通图具有电导 &phis;然后谣言传播，也称为随机广播，使用推拉策略以高概率在 O(log4 n/&phis;6) 步内成功广播消息。我们的方法的一个有趣的特点是，它在谣言传播和 Spielman 和 Teng 的光谱稀疏化过程之间建立了联系 [23]。
We show that if a connected graph with n nodes has conductance &phis; then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within O(log4 n/&phis;6) many steps, with high probability, using the PUSH-PULL strategy. An interesting feature of our approach is that it draws a connection between rumour spreading and the spectral sparsification procedure of Spielman and Teng [23].