English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Randomized Rumour Spreading: The Effect of the Network Topology

Panagiotou, K., Pérez-Giménez, X., Sauerwald, T., & Sun, H. (2015). Randomized Rumour Spreading: The Effect of the Network Topology. Combinatorics, Probability and Computing, 24(2), 457-479. doi:10.1017/s0963548314000194.

Item is

Basic

show hide
Genre: Journal Article
Latex : Randomized Rumour Spreading: {T}he Effect of the Network Topology

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Panagiotou, Konstantinos1, Author           
Pérez-Giménez, Xavier2, Author           
Sauerwald, Thomas1, Author           
Sun, He1, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: GRAPHS ALGORITHMS MATRICES Computer Science, Theory & Methods Mathematics Statistics & Probability
 Abstract: 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 log(2) n + logn + 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 log(2) n + gamma(c) log n with high probability, where gamma(c) = c log(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 = 2(d) vertices, the runtime is with high probability at least (1 + beta) . (log(2) n + log n), where beta > 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, c log n/n), where c is sufficiently close to 1.

Details

show
hide
Language(s): eng - English
 Dates: 20152015
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: Other: WOS:000348383500005
DOI: 10.1017/s0963548314000194
BibTex Citekey: PanagiotouCPC2015
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Combinatorics, Probability and Computing
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Cambridge : Cambridge University Press
Pages: - Volume / Issue: 24 (2) Sequence Number: - Start / End Page: 457 - 479 Identifier: ISSN: 0963-5483
CoNE: https://pure.mpg.de/cone/journals/resource/954925342763