Rumor spreading on random regular graphs and expanders

DOI10.1002/rsa.20432zbMath1272.05179arXiv1002.3518OpenAlexW2137662992MaRDI QIDQ2852547

Nikolaos Fountoulakis, Konstantinos D. Panagiotou

Publication date: 9 October 2013

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

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

zbMATH Keywords

random regular graphsexpandersrumor spreadingpseudorandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)

Related Items (7)

Stochastic analysis of rumor spreading with multiple pull operations ⋮ Asynchronous rumor spreading on random graphs ⋮ On the Push&Pull Protocol for Rumor Spreading ⋮ Continuous-time stochastic analysis of rumor spreading with multiple operations ⋮ Can the indifferent population affect the spread of rumors? ⋮ Dynamical behaviors of rumor spreading model with control measures ⋮ Probabilistic Analysis of Rumor-Spreading Time

Cites Work

• The shortest-path problem for graphs with random arc-lengths
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• On the second eigenvalue of a graph
• The asymptotic number of labeled graphs with given degree sequences
• Concentration of measure and isoperimetric inequalities in product spaces
• Concentration for Independent Permutations
• Randomized broadcast in networks
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• Quasi-random graphs
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Rumor spreading on random regular graphs and expanders