Push is Fast on Sparse Random Graphs

DOI10.1137/140984063zbMATH Open1364.05064arXiv1408.6378OpenAlexW2963973905MaRDI QIDQ2953404FDOQ2953404

Ueli Peter, Florian Meier

Publication date: 4 January 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider the classical push broadcast process on a large class of sparse random multigraphs that includes random power law graphs and multigraphs. Our analysis shows that for every $varepsilon>0$, whp $O(logn)$ rounds are sufficient to inform all but an $varepsilon$-fraction of the vertices. It is not hard to see that, e.g. for random power law graphs, the push process needs whp $n^{Omega(1)}$ rounds to inform all vertices. Fountoulakis, Panagiotou and Sauerwald proved that for random graphs that have power law degree sequences with $$, the push-pull protocol needs $Omega(logn)$ to inform all but $varepsilonn$ vertices whp. Our result demonstrates that, for such random graphs, the pull mechanism does not (asymptotically) improve the running time. This is surprising as it is known that, on random power law graphs with $$, push-pull is exponentially faster than pull.

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

zbMATH Keywords

social networksrandom graphsrumor spreadingbroadcasting protocols

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Social networks; opinion dynamics (91D30)

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The Probability That a Random Multigraph is Simple
• The Average Distance in a Random Graph with Given Expected Degrees
• Title not available (Why is that?)
• Probability and Computing
• The shortest-path problem for graphs with random arc-lengths
• Concentration of Measure for the Analysis of Randomized Algorithms
• The asymptotic number of labeled graphs with given degree sequences
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• Title not available (Why is that?)
• Randomized broadcast in networks
• Rumor Spreading on Random Regular Graphs and Expanders
• Social networks spread rumors in sublogarithmic time
• Rumor Spreading in Social Networks
• Almost tight bounds for rumour spreading with conductance
• Title not available (Why is that?)
• The diameter of sparse random graphs
• Title not available (Why is that?)

Cited In (1)

• The Push Tree problem

   Recommendations

• STACS 2004 👍 👎
• Matching algorithms are fast in sparse random graphs 👍 👎
• Fast scrambling on sparse graphs 👍 👎
• Push-Sum on Random Graphs: Almost Sure Convergence and Convergence Rate 👍 👎
• Implementing Huge Sparse Random Graphs 👍 👎
• Random perturbation of sparse graphs 👍 👎
• Fast graphs for the random walker 👍 👎
• Asymptotics for push on the complete graph 👍 👎
• Asymptotics for push on the complete graph 👍 👎

This page was built for publication: Push is Fast on Sparse Random Graphs

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