Randomized rumor spreading in poorly connected small‐world networks12. Issue 1 (19th November 2015)

• Record Type: Journal Article
• Authors: Mehrabian, Abbas; Pourmiri, Ali
• Is Part Of: Random structures & algorithms. Volume 49:Issue 1(2016)
• Page Start: 185
• Page End: 208
• Publication Date: 2015-11-19
• Subjects: randomized rumor spreading -- push‐pull protocol -- random k‐trees -- random k‐Apollonian networks -- urn models; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20624
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The Push‐Pull protocol is a well‐studied round‐robin rumor spreading protocol defined as follows: initially a node knows a rumor and wants to spread it to all nodes in a network quickly. In each round, every informed node sends the rumor to a random neighbor, and every uninformed node contacts a random neighbor and gets the rumor from her if she knows it. We analyze the behavior of this protocol on random k ‐trees, a class of power law graphs, which are small‐world and have large clustering coefficients, built as follows: initially we have a k ‐clique. In every step a new node is born, a random k ‐clique of the current graph is chosen, and the new node is joined to all nodes of the k ‐clique. When k ≥ 2 is fixed, we show that if initially a random node is aware of the rumor, then with probability 1 − o ( 1 ) after O ( ( log n ) 1 + 2 / k · log log n · f ( n ) ) rounds the rumor propagates to n − o ( n ) nodes, where n is the number of nodes and f ( n ) is any slowly growing function. Since these graphs have polynomially small conductance, vertex expansion O ( 1 / n ) and constant treewidth, these results demonstrate that Push‐Pull can be efficient even on poorly connected networks. On the negative side, we prove that with probability 1 − o ( 1 ) the protocol needs at least Ω ( n ( k − 1 ) / ( k 2 + k − 1 ) / f 2 ( n ) ) rounds to inform all nodes. This exponential dichotomy between time required for informing almost all and all nodes is striking. Our main contribution is to present, for the first time, a natural class of random graphs in which such a phenomenon can be observed. Our technique for proving the upper bound successfully carries over to a closely related class of graphs, the random k ‐Apollonian networks, for which we prove an upper bound of O ( ( log n ) c k · log log n · f ( n ) ) rounds for informing n − o ( n ) nodes with probability 1 − o ( 1 ) when k ≥ 3 is fixed. Here, c k = ( k 2 − 3 ) / ( k − 1 ) 2 < 1 + 2 / k © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 185–208, 2016