Rumour Spreading and Graph Conductance

Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi

Abstract

We show that if a connected graph with n nodes has conductance ϕ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within O(log4 n/ϕ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].
BibTeX
@inproceedings{chierichetti2010rumour,
  author = {Flavio Chierichetti and Silvio Lattanzi and Alessandro Panconesi},
  title = {{Rumour Spreading and Graph Conductance}},
  booktitle = {SODA},
  year = {2010},
  doi = {10.1137/1.9781611973075.135},
}

Loading related content...

Figure