Rumour spreading in dynamic random graphs

Abstract

We study rumour spreading in dynamic random graphs. Starting with a single informed vertex, the information flows until it reaches all the vertices of the graph (completion), according to the following process. At each step $k$, the information is propagated to neighbours, in the $k$-th generated random graph, of the informed vertices. The way this information propagates from vertex to vertex at each step will depend of the "protocol". First we consider a sequence of graphs in which the presence or absence of an edge follows the dynamic of a Markov chain. We provide a method based on strong stationary times allowing to bound the completion time for the Markov dynamic using bounds on the completion time in the i.i.d. dynamic.

We also consider the rumour spreading according to the Push Protocol (at every round, informed nodes send the rumour to one of their neighbours, chosen uniformly at random) in a sequence of independent stochastic block model random graphs. We are able to bound the completion time in this setting using comparisons with rumour spreading in dynamic random graphs with skeptical nodes (nodes that cannot become informed) and stifler nodes (nodes that, after being informed, do not spread the information further).