Rumor spreading in random evolving graphs

DOI10.1002/rsa.20586zbMath1381.05065WikidataQ58219121 ScholiaQ58219121MaRDI QIDQ2795745

Pierre Fraigniaud, Carola Doerr, Francesco Pasquale, Pierluigi Crescenzi, Riccardo Silvestri, Andrea E. F. Clementi

Publication date: 22 March 2016

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

Full work available at URL: https://doi.org/10.1002/rsa.20586

zbMATH Keywords

Markov chains; rumor spreading; dynamic random graphs; push protocol

Mathematics Subject Classification ID

05C82: Small world graphs, complex networks (graph-theoretic aspects)

05C80: Random graphs (graph-theoretic aspects)

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Random Walks on Randomly Evolving Graphs, Probabilistic Analysis of Rumor-Spreading Time, Reversible random walks on dynamic graphs, Continuous-time stochastic analysis of rumor spreading with multiple operations, Rumors' spread: a game theoretical approach with the replicator dynamics, On linear-time data dissemination in dynamic rooted trees, Stochastic analysis of rumor spreading with multiple pull operations, Asymptotics for pull on the complete graph

Cites Work

• Parsimonious flooding in dynamic graphs
• Broadcasting in dynamic radio networks
• The shortest-path problem for graphs with random arc-lengths
• Flooding Time of Edge-Markovian Evolving Graphs
• Randomized broadcast in networks
• On Spreading a Rumor
• Balanced Allocations
• Information Propagation Speed in Mobile and Delay Tolerant Networks
• Random Graphs