Randomized rumor spreading in poorly connected small‐world networks

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 ‐trees, a class of power law graphs, which are small‐world and have large clustering coefficients, built as follows: initially we have a ‐clique. In every step a new node is born, a random ‐clique of the current graph is chosen, and the new node is joined to all nodes of the ‐clique. When is fixed, we show that if initially a random node is aware of the rumor, then with probability after rounds the rumor propagates to nodes, where is the number of nodes and is any slowly growing function. Since these graphs have polynomially small conductance, vertex expansion 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 the protocol needs at least 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 ‐Apollonian networks, for which we prove an upper bound of rounds for informing nodes with probability when is fixed. Here, © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 185–208, 2016