TY - GEN
T1 - Social networks spread rumors in sublogarithmic time
AU - Doerr, Benjamin
AU - Fouz, Mahmoud
AU - Friedrich, Tobias
PY - 2011/1/1
Y1 - 2011/1/1
N2 - With the prevalence of social networks, it has become increasingly important to understand their features and limitations. It has been observed that information spreads extremely fast in social networks. We study the performance of randomized rumor spreading protocols on graphs in the preferential attachment model. The well-known random phone call model of Karp et al. (FOCS 2000) is a push-pull strategy where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following. • The push-pull strategy delivers a message to all nodes within Θ(log n) rounds with high probability. The best known bound so far was O(log2 n). • If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to Θ(log n / log log n), which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding double-contacts reduces the run-time to a smaller order of magnitude.
AB - With the prevalence of social networks, it has become increasingly important to understand their features and limitations. It has been observed that information spreads extremely fast in social networks. We study the performance of randomized rumor spreading protocols on graphs in the preferential attachment model. The well-known random phone call model of Karp et al. (FOCS 2000) is a push-pull strategy where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following. • The push-pull strategy delivers a message to all nodes within Θ(log n) rounds with high probability. The best known bound so far was O(log2 n). • If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to Θ(log n / log log n), which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding double-contacts reduces the run-time to a smaller order of magnitude.
KW - randomized algorithms
KW - rumor spreading
KW - social network
UR - https://www.scopus.com/pages/publications/79959760477
U2 - 10.1145/1993636.1993640
DO - 10.1145/1993636.1993640
M3 - Conference contribution
AN - SCOPUS:79959760477
SN - 9781450306911
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 21
EP - 30
BT - STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 43rd ACM Symposium on Theory of Computing, STOC 2011
Y2 - 6 June 2011 through 8 June 2011
ER -