1 Search Results for "Saribekyan, Hayk"

Document

DOI: 10.4230/LIPIcs.DISC.2020.9

Spread of Information and Diseases via Random Walks in Sparse Graphs

Authors: George Giakkoupis, Hayk Saribekyan, and Thomas Sauerwald

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

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 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].

Cite as

George Giakkoupis, Hayk Saribekyan, and Thomas Sauerwald. Spread of Information and Diseases via Random Walks in Sparse Graphs. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{giakkoupis_et_al:LIPIcs.DISC.2020.9,
  author =	{Giakkoupis, George and Saribekyan, Hayk and Sauerwald, Thomas},
  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 =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.9},
  URN =		{urn:nbn:de:0030-drops-130873},
  doi =		{10.4230/LIPIcs.DISC.2020.9},
  annote =	{Keywords: parallel random walks, information dissemination, infectious diseases}
}

Refine by Author
1 Giakkoupis, George
1 Saribekyan, Hayk
1 Sauerwald, Thomas

Refine by Classification
1 Mathematics of computing → Graph algorithms
1 Mathematics of computing → Stochastic processes
1 Theory of computation → Random walks and Markov chains

Refine by Keyword
1 infectious diseases
1 information dissemination
1 parallel random walks

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Saribekyan, Hayk"

Spread of Information and Diseases via Random Walks in Sparse Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message