Randomized rumour spreading: the effect of the network topology

DOI10.1017/S0963548314000194MaRDI QIDQ5364236zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Xavier Pérez-Giménez, Thomas Sauerwald, He Sun, Konstantinos Panagiotou

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548314000194

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Rumor spreading on random regular graphs and expanders
• Rumor spreading on random regular graphs and expanders
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• Quasirandom rumor spreading
• scientific article; zbMATH DE number 6783408

Cites work

• Almost tight bounds for rumour spreading with conductance
• Concentration of Measure for the Analysis of Randomized Algorithms
• Cover time and broadcast time
• Expander graphs and their applications
• Explicit construction of linear sized tolerant networks
• Fast Distributed Algorithms for Computing Separable Functions
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 5764860 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On the runtime and robustness of randomized broadcasting
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Probability and Computing
• Pseudo-random graphs
• Quasirandom load balancing
• Randomized broadcast in networks
• Rumor spreading and vertex expansion
• Rumor spreading on random regular graphs and expanders
• Spectral norm of random matrices
• The cover time of sparse random graphs
• The eigenvalues of random symmetric matrices
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The shortest-path problem for graphs with random arc-lengths
• Tight bounds for rumor spreading in graphs of a given conductance

Cited in

(17)

• Empirical study of the role of the topology in spreading on communication networks
• Stochastic analysis of rumor spreading with multiple pull operations
• Randomized rumor spreading in poorly connected small-world networks
• Rumor spreading on random regular graphs and expanders
• Rumor spreading on random regular graphs and expanders
• Robustness of randomized rumour spreading
• scientific article; zbMATH DE number 7525473 (Why is no real title available?)
• Propagation time for probabilistic zero forcing
• Probabilistic Analysis of Rumor-Spreading Time
• Tight analysis of randomized rumor spreading in complete graphs
• Rumour spreading and graph conductance
• Rumor spreading and vertex expansion
• Asymptotics for push on the complete graph
• Asymptotics for push on the complete graph
• Continuous-time stochastic analysis of rumor spreading with multiple operations
• Rumors with changing credibility
• On mixing and edge expansion properties in randomized broadcasting

This page was built for publication: Randomized rumour spreading: the effect of the network topology

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