Paper Info
Title
Ultra-fast rumor spreading in social networks
Abstract
We analyze the popular push-pull protocol for spreading a rumor in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graphs that have a power law degree distribution with an arbitrary exponent β 2. Our main findings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, we show that if 2 β n) rounds with high probability. On the other hand, if β 3, then Ω(log n) rounds are necessary. We also investigate the asynchronous version of the push-pull protocol, where the nodes do not operate in rounds, but exchange information according to a Poisson process with rate 1. Surprisingly, we are able to show that, if 2 β constant time, which is much smaller than the typical distance of two nodes. To the best of our knowledge, this is the first result that establishes a gap between the synchronous and the asynchronous protocol.
Year
DOI
Venue
2012
10.5555/2095116.2095246
SODA
Keywords
Field
DocType
social network,random graph,power law,asynchronous version,single node,power law degree distribution,arbitrary exponent,ultra-fast rumor,random neighbor,asynchronous protocol,popular push-pull protocol,push-pull protocol
Discrete mathematics,Asynchronous communication,Binary logarithm,Social network,Random graph,Exponent,Computer science,Rumor,Poisson process,Power law
Conference
ISBN
Citations 
PageRank 
978-1-61197-251-1
28
0.91
References 
Authors
20
3
Name
Order
Citations
PageRank
Nikolaos Fountoulakis118518.04
Konstantinos Panagiotou229027.80
Thomas Sauerwald357539.99