Randomized rumor spreading in poorly connected small-world networks

DOI10.1002/RSA.20624zbMATH Open1344.05129arXiv1410.8175OpenAlexW2917208934MaRDI QIDQ2818280FDOQ2818280

Authors: Abbas Mehrabian, Ali Pourmiri 

Publication date: 7 September 2016

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: 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 $Oleft((logn{)}^{1+2/k}cdotloglogncdotf(n)ight)$ 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 $Omegaleft(n^{(k-1)/(k^2+k-1)}/f^2(n)ight)$ 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 $Oleft((logn{)}^{c_k}cdotloglogncdotf(n)ight)$ rounds for informing $n-o(n)$ nodes with probability $1-o(1)$ when $k>2$ is fixed. Here, $c_k=(k^2-3)/(k-1{)}^2<1+2/k$.

Full work available at URL: https://arxiv.org/abs/1410.8175

Recommendations

• Ultra-fast rumor spreading in social networks
• Faster rumor spreading with multiple calls
• Rumor spreading in social networks
• Rumor Spreading in Social Networks
• On the Push\&Pull protocol for rumour spreading (extended abstract)

zbMATH Keywords

urn modelsrandomized rumor spreadingpush-pull protocolrandom \(k\)-Apollonian networksrandom \(k\)-trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Collective dynamics of `small-world' networks
• Random Trees
• A survey of gossiping and broadcasting in communication networks
• Some exactly solvable models of urn process theory
• The Spectra of Random Graphs with Given Expected Degrees
• Treewidth. Computations and approximations
• Title not available (Why is that?)
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Limit theorems for triangular urn schemes
• Randomized broadcast in networks
• Rumor spreading on random regular graphs and expanders
• Social networks spread rumors in sublogarithmic time
• Rumor Spreading in Social Networks
• Further Inequalities for the Gamma Function
• The degree distribution of random \(k\)-trees
• The height of random k‐trees and related branching processes
• Scale free properties of random \(k\)-trees
• High-dimensional Apollonian networks
• Resource discovery in distributed networks
• Randomized rumour spreading: the effect of the network topology
• Asynchronous Rumor Spreading in Preferential Attachment Graphs

Cited In (5)

• Probabilistic zero forcing on random graphs
• Global computation in a poorly connected world
• ILSCR rumor spreading model to discuss the control of rumor spreading in emergency
• Bounds on expected propagation time of probabilistic zero forcing
• On the Push&Pull Protocol for Rumor Spreading

This page was built for publication: Randomized rumor spreading in poorly connected small-world networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2818280)