License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.57
URN: urn:nbn:de:0030-drops-29977
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/2997/
Go to the corresponding LIPIcs Volume Portal

Giakkoupis, George

Tight bounds for rumor spreading in graphs of a given conductance

pdf-format:
9.pdf (0.6 MB)

Abstract

We study the connection between the rate at which a rumor spreads throughout a graph and the conductance of the graph -- a standard measure of a graph's expansion properties.
We show that for any n-node graph with conductance phi, the classical PUSH-PULL algorithm distributes a rumor to all nodes of the graph in O(phi^(-1) log(n)) rounds with high probability (w.h.p.). This bound improves a recent result of Chierichetti, Lattanzi, and Panconesi [STOC 2010], and it is tight in the sense that there exist graphs where Omega(phi^(-1)log(n)) rounds of the PUSH-PULL algorithm are required to distribute a rumor w.h.p.

We also explore the PUSH and the PULL algorithms, and derive conditions that are both necessary and sufficient for the above upper bound to hold for those algorithms as well.
An interesting finding is that every graph contains a node such that the PULL algorithm takes O(phi^(-1) log(n)) rounds w.h.p. to distribute a rumor started at that node.
In contrast, there are graphs where the PUSH algorithm requires significantly more rounds for any start node.

BibTeX - Entry

@InProceedings{giakkoupis:LIPIcs:2011:2997,
  author =	{George Giakkoupis},
  title =	{{Tight bounds for rumor spreading in graphs of a given conductance}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{57--68},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/2997},
  URN =		{urn:nbn:de:0030-drops-29977},
  doi =		{10.4230/LIPIcs.STACS.2011.57},
  annote =	{Keywords: conductance, rumor spreading}
}

Keywords: conductance, rumor spreading
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI