Rumor spreading and vertex expansion
George Giakkoupis, Thomas Sauerwald · 2012
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 O(α −1 log 2 n √ log n) rounds with high probability. Further, we construct graphs for which Ω(α −1 log 2 n) rounds are needed. Our results complement a long series of works that relate rumor spreading to edgebased notions of expansion, resolving one of the most natural questions on the connection between rumor spreading and expansion. 1