caa a22 4500 445822635 CHVBK 20180317145248.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s10626-010-0092-5 doi (NATIONALLICENCE)springer-10.1007/s10626-010-0092-5 A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents [Elektronische Daten] [Moez Draief, Ayalvadi Ganesh] 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 Science+Business Media, LLC, 2010 Random walks on graphs nationallicence Power-law graphs nationallicence Erdős-Rényi graph nationallicence Regular graphs nationallicence Infection time nationallicence Draief Moez Department of Electrical Engineering, Imperial College London, SW7 2AZ, South Kensington, UK aut Ganesh Ayalvadi Department of Mathematics, Bristol University, BS8 1TW, Bristol, UK aut Discrete Event Dynamic Systems Springer US; http://www.springer-ny.com 21/1(2011-03-01), 41-61 0924-6703 21:1<41 2011 21 10626 https://doi.org/10.1007/s10626-010-0092-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10626-010-0092-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Draief Moez Department of Electrical Engineering, Imperial College London, SW7 2AZ, South Kensington, UK aut NATIONALLICENCE 700 1- Ganesh Ayalvadi Department of Mathematics, Bristol University, BS8 1TW, Bristol, UK aut NATIONALLICENCE 773 0- Discrete Event Dynamic Systems Springer US; http://www.springer-ny.com 21/1(2011-03-01), 41-61 0924-6703 21:1<41 2011 21 10626 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer