Rumor spreading in random evolving graphs

DOI10.1002/rsa.20586zbMath1381.05065OpenAlexW2044104876WikidataQ58219121 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 chainsrumor spreadingdynamic random graphspush protocol

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Stochastic analysis of rumor spreading with multiple pull operations, Random Walks on Randomly Evolving Graphs, 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, Can the indifferent population affect the spread of rumors?, Asymptotics for pull on the complete graph, On linear-time data dissemination in dynamic rooted trees, Probabilistic Analysis of Rumor-Spreading Time, Unnamed Item

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