Push is Fast on Sparse Random Graphs

DOI10.1137/140984063MaRDI QIDQ2953404zbMATH OpenOpenAlexFDO

Authors Florian Meier, Ueli Peter

Publication date 4 January 2017

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 747040 (Why is no real title available?)
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Almost tight bounds for rumour spreading with conductance
• Concentration of Measure for the Analysis of Randomized Algorithms
• Probability and Computing
• Randomized broadcast in networks
• Rumor Spreading in Social Networks
• Rumor spreading on random regular graphs and expanders
• Rumour spreading and graph conductance
• Social networks spread rumors in sublogarithmic time
• The Average Distance in a Random Graph with Given Expected Degrees
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The asymptotic number of labeled graphs with given degree sequences
• The diameter of sparse random graphs
• The probability that a random multigraph is simple
• The shortest-path problem for graphs with random arc-lengths
• Tight bounds for rumor spreading in graphs of a given conductance
• Ultra-fast rumor spreading in social networks

Cited in

(1)

• The Push Tree problem

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)