License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.9
URN: urn:nbn:de:0030-drops-130873
Go to the corresponding LIPIcs Volume Portal

Giakkoupis, George ; Saribekyan, Hayk ; Sauerwald, Thomas

Spread of Information and Diseases via Random Walks in Sparse Graphs

LIPIcs-DISC-2020-9.pdf (0.5 MB)


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. [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 well-studied randomized rumor spreading process, on any d-regular graph with d = Ω(log n). The case of sub-logarithmic 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 3-regular 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 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(log n), w.h.p., for constant-degree 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 k-dimensional grids (k ≥ 1 is constant), by adapting a technique by Kesten and Sidoravicius [Kesten and Sidoravicius, 2003; Kesten and Sidoravicius, 2005].

BibTeX - Entry

  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:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-130873},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI