{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T11:49:18Z","timestamp":1759664958785},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,5,6]],"date-time":"2014-05-06T00:00:00Z","timestamp":1399334400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,3]]},"abstract":"<jats:p>We consider the popular and well-studied push model, which is used to spread information in a given network with <jats:italic>n<\/jats:italic> 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 <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>) 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 <jats:italic>n<\/jats:italic> vertices with small spectral expansion, rumour spreading completes after log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic> + log <jats:italic>n<\/jats:italic>+<jats:italic>o<\/jats:italic>(log <jats:italic>n<\/jats:italic>) 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 <jats:italic>G(n,p)<\/jats:italic> with <jats:italic>p=c<\/jats:italic> log <jats:italic>n\/n<\/jats:italic>, where <jats:italic>c<\/jats:italic> &gt; 1, we determine the runtime of rumour spreading to be log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic> + \u03b3 (<jats:italic>c<\/jats:italic>)log <jats:italic>n<\/jats:italic> with high probability, where \u03b3(<jats:italic>c<\/jats:italic>) = <jats:italic>c<\/jats:italic>log(<jats:italic>c<\/jats:italic>\/(<jats:italic>c<\/jats:italic>\u22121)). In particular, this shows that the assumption of almost regularity in our first result is necessary. Finally, for a hypercube on <jats:italic>n<\/jats:italic>=2<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> vertices, the runtime is with high probability at least (1+\u03b2) \u22c5 (log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic> + log <jats:italic>n<\/jats:italic>), where \u03b2 &gt; 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 <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>) for the hypercube (see [11]) imply that the push model is faster on hypercubes than on a random graph <jats:italic>G<\/jats:italic>(<jats:italic>n, c<\/jats:italic>log <jats:italic>n\/n<\/jats:italic>), where <jats:italic>c<\/jats:italic> is sufficiently close to 1.<\/jats:p>","DOI":"10.1017\/s0963548314000194","type":"journal-article","created":{"date-parts":[[2014,5,6]],"date-time":"2014-05-06T10:52:06Z","timestamp":1399373526000},"page":"457-479","source":"Crossref","is-referenced-by-count":14,"title":["Randomized Rumour Spreading: The Effect of the Network Topology"],"prefix":"10.1017","volume":"24","author":[{"given":"KONSTANTINOS","family":"PANAGIOTOU","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"XAVIER","family":"P\u00c9REZ-GIM\u00c9NEZ","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"THOMAS","family":"SAUERWALD","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HE","family":"SUN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,5,6]]},"reference":[{"key":"S0963548314000194_ref5","doi-asserted-by":"crossref","unstructured":"Chierichetti F. , Lattanzi S. and Panconesi A. (2010) Almost tight bounds for rumour spreading with conductance. In 42nd Annual ACM Symposium on Theory of Computing: STOC'10, pp. 399\u2013408.","DOI":"10.1145\/1806689.1806745"},{"key":"S0963548314000194_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548314000194_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"S0963548314000194_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20151"},{"key":"S0963548314000194_ref18","doi-asserted-by":"crossref","unstructured":"Giakkoupis G. and Sauerwald T. (2012) Rumor spreading and vertex expansion. In 23rd Annual ACM-SIAM Symposium on Discrete Algorithms: SODA'12,, pp. 1623\u20131641.","DOI":"10.1137\/1.9781611973099.129"},{"key":"S0963548314000194_ref12","doi-asserted-by":"crossref","unstructured":"Fountoulakis N. and Panagiotou K. (2010) Rumor spreading on random regular graphs and expanders. In 14th International Workshop on Randomization and Computation: RANDOM'10, pp. 560\u2013573.","DOI":"10.1007\/978-3-642-15369-3_42"},{"key":"S0963548314000194_ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"S0963548314000194_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"S0963548314000194_ref21","doi-asserted-by":"crossref","unstructured":"Karp R. , Schindelhauer C. , Shenker S. and V\u00f6cking B. (2000) Randomized rumor spreading. In 41st Annual IEEE Symposium on Foundations of Computer Science: FOCS'00, pp. 565\u2013574.","DOI":"10.1109\/SFCS.2000.892324"},{"key":"S0963548314000194_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2190-z"},{"key":"S0963548314000194_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.924648"},{"key":"S0963548314000194_ref7","unstructured":"Doerr B. , Friedrich T. and Sauerwald T. (2008) Quasirandom rumor spreading. In 19th Annual ACM-SIAM Symposium on Discrete Algorithms: SODA'08, pp. 773\u2013781. arXiv.1012.5351"},{"key":"S0963548314000194_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290805"},{"key":"S0963548314000194_ref13","doi-asserted-by":"crossref","unstructured":"Fountoulakis N. , Huber A. and Panagiotou K. (2010) Reliable broadcasting in random networks and the effect of density. In 29th IEEE Conference on Computer Communications: INFOCOM'10, pp. 2552\u20132560.","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"S0963548314000194_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.017"},{"key":"S0963548314000194_ref23","first-page":"148","volume-title":"Surveys in Combinatorics","author":"McDiarmid","year":"1989"},{"key":"S0963548314000194_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/100799216"},{"key":"S0963548314000194_ref19","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S0963548314000194_ref17","unstructured":"Giakkoupis G. (2011) Tight upper bounds for rumor spreading in graphs of a given conductance. In 28th International Symposium on Theoretical Aspects of Computer Science: STACS'11, pp. 57\u201368."},{"key":"S0963548314000194_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"S0963548314000194_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"S0963548314000194_ref10","unstructured":"Els\u00e4sser R. and Sauerwald T. (2009) Cover time and broadcast time. In 26th International Symposium on Theoretical Aspects of Computer Science: STACS'09, pp. 373\u2013384."},{"key":"S0963548314000194_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"S0963548314000194_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"S0963548314000194_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"S0963548314000194_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719512"},{"key":"S0963548314000194_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T22:51:40Z","timestamp":1555800700000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000194\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,6]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["S0963548314000194"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000194","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,6]]}}}