Push is Fast on Sparse Random Graphs

DOI10.1137/140984063zbMath1364.05064arXiv1408.6378OpenAlexW2963973905MaRDI QIDQ2953404

Ueli Peter, Florian Meier

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

random graphssocial networksrumor spreadingbroadcasting protocols

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The shortest-path problem for graphs with random arc-lengths
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Almost tight bounds for rumour spreading with conductance
• Randomized broadcast in networks
• The Probability That a Random Multigraph is Simple
• Rumor Spreading on Random Regular Graphs and Expanders
• Rumor Spreading in Social Networks
• 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
• The Average Distance in a Random Graph with Given Expected Degrees
• Social networks spread rumors in sublogarithmic time
• The diameter of sparse random graphs
• Probability and Computing
• Concentration of Measure for the Analysis of Randomized Algorithms