Document Open Access Logo

Spread of Information and Diseases via Random Walks in Sparse Graphs

Authors George Giakkoupis, Hayk Saribekyan, Thomas Sauerwald

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.9.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

George Giakkoupis
  • Inria, Université Rennes, CNRS, IRISA, Rennes, France
Hayk Saribekyan
  • University of Cambridge, UK
Thomas Sauerwald
  • University of Cambridge, UK

Funding

  • Giakkoupis, George: Supported in part by ANR Project PAMELA (ANR16-CE23-0016-01).
  • Saribekyan, Hayk: Gates Cambridge Scholarship programme.
  • Sauerwald, Thomas: Supported by the ERC Grant "Dynamic March".

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.DISC.2020.9

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

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Stochastic processes
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Graph algorithms
Keywords
  • parallel random walks
  • information dissemination
  • infectious diseases

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Proc. 20th IEEE Symposium on Foundations of Computer Science, FOCS, pages 218-223, 1979. URL: https://doi.org/10.1109/SFCS.1979.34.
  2. Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, and Mark R. Tuttle. Many random walks are faster than one. Combinatorics, Probability & Computing, 20(4):481-502, 2011. URL: https://doi.org/10.1017/S0963548311000125.
  3. O. S. M. Alves, F. P. Machado, and S. Yu. Popov. The shape theorem for the frog model. The Annals of Applied Probability, 12(2):533–546, May 2002. URL: https://doi.org/10.1214/aoap/1026915614.
  4. Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, and Eli Upfal. Trading space for time in undirected s-t connectivity. SIAM J. Comput., 23(2):324-334, 1994. URL: https://doi.org/10.1137/S0097539790190144.
  5. Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, and Alessandro Panconesi. Rumor spreading and conductance. J. ACM, 65(4):17:1-17:21, 2018. URL: https://doi.org/10.1145/3173043.
  6. Fan R. K. Chung and Lincoln Lu. Concentration inequalities and martingale inequalities: A survey. Internet Mathematics, 3(1):79-127, 2006. URL: https://doi.org/10.1080/15427951.2006.10129115.
  7. Colin Cooper. Random walks, interacting particles, dynamic networks: Randomness can be helpful. In Proc. 18th International Colloquium on Structural Information and Communication Complexity, SIROCCO, pages 1-14, 2011. URL: https://doi.org/10.1007/978-3-642-22212-2_1.
  8. Colin Cooper, Alan M. Frieze, and Tomasz Radzik. Multiple random walks in random regular graphs. SIAM J. Discrete Math., 23(4):1738-1761, 2009. URL: https://doi.org/10.1137/080729542.
  9. Alan J. Demers, Daniel H. Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard E. Sturgis, Daniel C. Swinehart, and Douglas B. Terry. Epidemic algorithms for replicated database maintenance. Operating Systems Review, 22(1):8-32, 1988. URL: https://doi.org/10.1145/43921.43922.
  10. Tassos Dimitriou, Sotiris E. Nikoletseas, and Paul G. Spirakis. The infection time of graphs. Discrete Applied Mathematics, 154(18):2577-2589, 2006. URL: https://doi.org/10.1016/j.dam.2006.04.026.
  11. Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich. Social networks spread rumors in sublogarithmic time. In Proc. 43rd ACM Symposium on Theory of Computing, STOC, pages 21-30, 2011. URL: https://doi.org/10.1145/1993636.1993640.
  12. Klim Efremenko and Omer Reingold. How well do random walks parallelize? In Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 476-489, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_36.
  13. Robert Elsässer and Thomas Sauerwald. Tight bounds for the cover time of multiple random walks. Theor. Comput. Sci., 412(24):2623-2641, 2011. URL: https://doi.org/10.1016/j.tcs.2010.08.010.
  14. Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. Randomized broadcast in networks. Random Struct. Algorithms, 1(4):447-460, 1990. URL: https://doi.org/10.1002/rsa.3240010406.
  15. William Feller. An Introduction to Probability Theory and its Applications. Vol. 1. Wiley series in probability and mathematical statistics. Wiley, 1968. Google Scholar
  16. George Giakkoupis, Frederik Mallmann-Trenn, and Hayk Saribekyan. How to spread a rumor: Call your neighbors or take a walk? In Proc. 38th ACM Symposium on Principles of Distributed Computing, PODC, pages 24-33, 2019. URL: https://doi.org/10.1145/3293611.3331622.
  17. George Giakkoupis, Frederik Mallmann-Trenn, and Hayk Saribekyan. How to spread a rumor: Call your neighbors or take a walk? CoRR, abs/2006.02368, 2020. URL: http://arxiv.org/abs/2006.02368.
  18. George Giakkoupis, Hayk Saribekyan, and Thomas Sauerwald. Spread of information and diseases via random walks in sparse graphs. Research report, Inria, August 2020. URL: https://hal.inria.fr/hal-02913942.
  19. Peter Gracar and Alexandre Stauffer. Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents. In Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 116 of LIPIcs, pages 39:1-39:17, 2018. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.39.
  20. Jonathan Hermon. Frogs on trees? Electron. J. Probab., 23:40 pp., 2018. URL: https://doi.org/10.1214/18-EJP144.
  21. Richard M. Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vöcking. Randomized rumor spreading. In Proc. 41st IEEE Symposium on Foundations of Computer Science, FOCS, pages 565-574, 2000. URL: https://doi.org/10.1109/SFCS.2000.892324.
  22. Harry Kesten and Vladas Sidoravicius. Branching random walk with catalysts. Electronic Journal of Probability, 8(0), 2003. URL: https://doi.org/10.1214/EJP.v8-127.
  23. Harry Kesten and Vladas Sidoravicius. The spread of a rumor or infection in a moving population. The Annals of Probability, 33(6):2402–2462, November 2005. Zbl: 1111.60074. URL: https://doi.org/10.1214/009117905000000413.
  24. Harry Kesten and Vladas Sidoravicius. A shape theorem for the spread of an infection. Annals of Mathematics, 167(3):701–766, May 2008. URL: https://doi.org/10.4007/annals.2008.167.701.
  25. Axel Kramer, Ingeborg Schwebke, and Günter Kampf. How long do nosocomial pathogens persist on inanimate surfaces? A systematic review. BMC Infectious Diseases, 6(1):130, December 2006. URL: https://doi.org/10.1186/1471-2334-6-130.
  26. Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, and Yajun Wang. Information dissemination via random walks in d-dimensional space. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1612-1622, 2012. URL: https://doi.org/10.1137/1.9781611973099.128.
  27. Russell Lyons and Shayan Oveis Gharan. Sharp bounds on random walk eigenvalues via spectral embedding. International Mathematics Research Notices, 2018(24):7555-7605, May 2017. URL: https://doi.org/10.1093/imrn/rnx082.
  28. Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci, and Eli Upfal. Infectious random walks. CoRR, abs/1007.1604:21 pp., 2010. URL: http://arxiv.org/abs/1007.1604.
  29. Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci, and Eli Upfal. Tight bounds on information dissemination in sparse mobile networks. In Proc. 30th ACM Symposium on Principles of Distributed Computing, PODC, pages 355-362, 2011. URL: https://doi.org/10.1145/1993806.1993882.
  30. Serguei Yu. Popov. Frogs and some other interacting random walks models. In Proc. Discrete Random Walks, DRW, pages 277-288, 2003. URL: http://dmtcs.episciences.org/3328.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact