Skip to Main content Skip to Navigation
Conference papers

Spread of Information and Diseases via Random Walks in Sparse Graphs

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. (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 = \Omega(\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 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 $\Omega(\log^2 n/ \log \log n)$, whereas randomized rumor spreading is completed in time $\Theta(\log n)$, w.h.p. Next, we show a general upper bound of $\tilde O(d \cdot diam(G) + \log^3 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 \cdot \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, by adapting a technique by Kesten and Sidoravicius.
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-02913942
Contributor : George Giakkoupis <>
Submitted on : Tuesday, August 11, 2020 - 12:37:00 AM
Last modification on : Thursday, January 7, 2021 - 4:35:40 PM
Long-term archiving on: : Monday, November 30, 2020 - 5:26:51 PM

File

visitxld.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02913942, version 1

Citation

George Giakkoupis, Hayk Saribekyan, Thomas Sauerwald. Spread of Information and Diseases via Random Walks in Sparse Graphs. DISC 2020 - 34rd International Symposium on Distributed Computing, Oct 2020, Freiburg, Germany. pp.1-42. ⟨hal-02913942⟩

Share

Metrics

Record views

173

Files downloads

259