Abstract
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 nvertex 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. [George Giakkoupis et al., 2019] 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 wellstudied randomized rumor spreading process, on any dregular graph with d = Ω(log n). The case of sublogarithmic degree was left open, and is the main focus of this paper.
First, we observe that the equivalence shown in [George Giakkoupis et al., 2019] does not hold for small d: We give an example of a 3regular graph with logarithmic diameter for which the expected spreading time is Ω(log² n/log log n), whereas randomized rumor spreading is completed in time Θ(log n), w.h.p. Next, we show a general upper bound of Õ(d ⋅ diam(G) + log³ n /d), w.h.p., for the spreading time on any dregular graph. We also provide a version of the bound based on the average degree, for nonregular graphs. Next, we give tight analyses for specific graph families. We show that the spreading time is O(log n), w.h.p., for constantdegree regular expanders. For the binary tree, we show an upper bound of O(log n⋅ log log n), 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 kdimensional grids (k ≥ 1 is constant), by adapting a technique by Kesten and Sidoravicius [Kesten and Sidoravicius, 2003; Kesten and Sidoravicius, 2005].
BibTeX  Entry
@InProceedings{giakkoupis_et_al:LIPIcs:2020:13087,
author = {George Giakkoupis and Hayk Saribekyan and Thomas Sauerwald},
title = {{Spread of Information and Diseases via Random Walks in Sparse Graphs}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {9:19:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771689},
ISSN = {18688969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13087},
URN = {urn:nbn:de:0030drops130873},
doi = {10.4230/LIPIcs.DISC.2020.9},
annote = {Keywords: parallel random walks, information dissemination, infectious diseases}
}
Keywords: 

parallel random walks, information dissemination, infectious diseases 
Collection: 

34th International Symposium on Distributed Computing (DISC 2020) 
Issue Date: 

2020 
Date of publication: 

07.10.2020 