Cargando…
A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents
We address the question of understanding the effect of the underlying network topology on the spread of a virus and the dissemination of information when users are mobile performing independent random walks on a graph. To this end, we propose a simple model of infection that enables to study the coi...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer US
2010
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7088300/ https://www.ncbi.nlm.nih.gov/pubmed/32214674 http://dx.doi.org/10.1007/s10626-010-0092-5 |
_version_ | 1783509512862302208 |
---|---|
author | Draief, Moez Ganesh, Ayalvadi |
author_facet | Draief, Moez Ganesh, Ayalvadi |
author_sort | Draief, Moez |
collection | PubMed |
description | We address the question of understanding the effect of the underlying network topology on the spread of a virus and the dissemination of information when users are mobile performing independent random walks on a graph. To this end, we propose a simple model of infection that enables to study the coincidence time of two random walkers on an arbitrary graph. By studying the coincidence time of a susceptible and an infected individual both moving in the graph we obtain estimates of the infection probability. The main result of this paper is to pinpoint the impact of the network topology on the infection probability. More precisely, we prove that for homogeneous graphs including regular graphs and the classical Erdős–Rényi model, the coincidence time is inversely proportional to the number of nodes in the graph. We then study the model on power-law graphs, that exhibit heterogeneous connectivity patterns, and show the existence of a phase transition for the coincidence time depending on the parameter of the power-law of the degree distribution. We finally undertake a preliminary analysis for the case with k random walkers and provide upper bounds on the convergence time for both the complete graph and regular graphs. |
format | Online Article Text |
id | pubmed-7088300 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2010 |
publisher | Springer US |
record_format | MEDLINE/PubMed |
spelling | pubmed-70883002020-03-23 A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents Draief, Moez Ganesh, Ayalvadi Discret Event Dyn Syst Article We address the question of understanding the effect of the underlying network topology on the spread of a virus and the dissemination of information when users are mobile performing independent random walks on a graph. To this end, we propose a simple model of infection that enables to study the coincidence time of two random walkers on an arbitrary graph. By studying the coincidence time of a susceptible and an infected individual both moving in the graph we obtain estimates of the infection probability. The main result of this paper is to pinpoint the impact of the network topology on the infection probability. More precisely, we prove that for homogeneous graphs including regular graphs and the classical Erdős–Rényi model, the coincidence time is inversely proportional to the number of nodes in the graph. We then study the model on power-law graphs, that exhibit heterogeneous connectivity patterns, and show the existence of a phase transition for the coincidence time depending on the parameter of the power-law of the degree distribution. We finally undertake a preliminary analysis for the case with k random walkers and provide upper bounds on the convergence time for both the complete graph and regular graphs. Springer US 2010-08-17 2011 /pmc/articles/PMC7088300/ /pubmed/32214674 http://dx.doi.org/10.1007/s10626-010-0092-5 Text en © Springer Science+Business Media, LLC 2010 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic. |
spellingShingle | Article Draief, Moez Ganesh, Ayalvadi A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents |
title | A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents |
title_full | A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents |
title_fullStr | A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents |
title_full_unstemmed | A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents |
title_short | A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents |
title_sort | random walk model for infection on graphs: spread of epidemics & rumours with mobile agents |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7088300/ https://www.ncbi.nlm.nih.gov/pubmed/32214674 http://dx.doi.org/10.1007/s10626-010-0092-5 |
work_keys_str_mv | AT draiefmoez arandomwalkmodelforinfectionongraphsspreadofepidemicsrumourswithmobileagents AT ganeshayalvadi arandomwalkmodelforinfectionongraphsspreadofepidemicsrumourswithmobileagents AT draiefmoez randomwalkmodelforinfectionongraphsspreadofepidemicsrumourswithmobileagents AT ganeshayalvadi randomwalkmodelforinfectionongraphsspreadofepidemicsrumourswithmobileagents |