Spread of Information and Diseases via Random Walks in Sparse Graphs

We consider a natural network diffusion process, modeling the spread of information or infectious diseases. Multiple mobile agents perform independent simple random walks on an n-vertex connected graph G. The number of agents is linear in n and the walks start from the stationary distribution. Initially, a single vertex has a piece of information (or a virus). An agent becomes informed (or infected) the first time it visits some vertex with the information (or virus); thereafter, the agent informs (infects) all vertices it visits. Giakkoupis et al. (PODC'19) have shown that the spreading time, i.e., the time before all vertices are informed, is asymptotically and w.h.p. the same as in the well-studied randomized rumor spreading process, on any d-regular graph with d=Ω(logn). The case of sub-logarithmic degree was left open, and is the main focus of this paper. First, we observe that the equivalence shown by Giakkoupis et al. does not hold for small d: We give an example of a 3-regular graph with logarithmic diameter for which the expected spreading time is Ω(log^2n/loglogn), whereas randomized rumor spreading is completed in time Θ(logn), w.h.p. Next, we show a general upper bound of O~(d⋅diam(G)+log^3n/d), w.h.p., for the spreading time on any d-regular graph. We also provide a version of the bound based on the average degree, for non-regular graphs. Next, we give tight analyses for specific graph families. We show that the spreading time is O(logn), w.h.p., for constant-degree regular expanders. For the binary tree, we show an upper bound of O(logn⋅loglogn), w.h.p., and prove that this is tight, by giving a matching lower bound for the cover time of the tree by n random walks. Finally, we show a bound of O(diam(G)), w.h.p., for k-dimensional grids, by adapting a technique by Kesten and Sidoravicius.Supported in part by ANR Project PAMELA (ANR16-CE23-0016-01). Gates Cambridge Scholarship programme. Supported by the ERC Grant `Dynamic March’