文章基本信息

标题：Spread of Information and Diseases via Random Walks in Sparse Graphs
本地全文：下载
作者：George Giakkoupis ; Hayk Saribekyan ; Thomas Sauerwald 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-17
DOI：10.4230/LIPIcs.DISC.2020.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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].
关键词：parallel random walks; information dissemination; infectious diseases