%0 Conference Paper %1 Ganesh:2009:RWM:1698822.1698866 %A Ganesh, A. %A Draief, M. %B Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools %C ICST, Brussels, Belgium, Belgium %D 2009 %I ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) %K infection random walk %P 34:1--34:8 %R 10.4108/ICST.VALUETOOLS2009.7447 %T A random walk model for infection on graphs %U http://dx.doi.org/10.4108/ICST.VALUETOOLS2009.7447 %X 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.</p> <p>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 graph including regular graphs and the classical Erd&ouml;s-R&eacute;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. %@ 978-963-9799-70-7

@inproceedings{Ganesh:2009:RWM:1698822.1698866, abstract = {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.</p> <p>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 graph including regular graphs and the classical Erd&ouml;s-R&eacute;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.}, acmid = {1698866}, added-at = {2012-04-05T00:05:33.000+0200}, address = {ICST, Brussels, Belgium, Belgium}, articleno = {34}, author = {Ganesh, A. and Draief, M.}, biburl = {https://www.bibsonomy.org/bibtex/2db4c6460f7cf233e4c38454f1bb4602b/emrahcem}, booktitle = {Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools}, description = {A random walk model for infection on graphs}, doi = {10.4108/ICST.VALUETOOLS2009.7447}, interhash = {3c3ed09e17a277858f5636a78a754fb9}, intrahash = {db4c6460f7cf233e4c38454f1bb4602b}, isbn = {978-963-9799-70-7}, keywords = {infection random walk}, location = {Pisa, Italy}, numpages = {8}, pages = {34:1--34:8}, publisher = {ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)}, series = {VALUETOOLS '09}, timestamp = {2012-04-05T00:05:33.000+0200}, title = {A random walk model for infection on graphs}, url = {http://dx.doi.org/10.4108/ICST.VALUETOOLS2009.7447}, year = 2009 }