Rumor spreading and vertex expansion

Pages: 1623 - 1641
Published: Jan 17, 2012
Abstract
We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n-node graph with vertex expansion α, we show that this protocol spreads a rumor from a single node to all other nodes in [EQUATION] rounds with high probability....
Paper Details
Title
Rumor spreading and vertex expansion
Published Date
Jan 17, 2012
Journal
Pages
1623 - 1641
Citation AnalysisPro
  • Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
  • Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.