2014/10/29 by Abbas Mehrabian, Mehrabian, Abbas, Ali Pourmiri +1 · 2 citations
Computer Science · Physics and Astronomy · #Caching and Content Delivery #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Opportunistic and Delay-Tolerant Networks #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1410.8175
openalex publication_date 2014/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Push-Pull 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 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>1 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⋅loglog 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)/(k2+k-1)/f2(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 carries over to a closely related class of graphs, random k-Apollonian networks, for which we prove an upper bound of O((log n)ck⋅loglog n⋅ f(n)) rounds for informing n-o(n) nodes with probability 1-o(1) when k>2 is fixed. Here, ck=(k2-3)/(k-1)2<1 + 2/k.