Broadcasting in  Small-World Communication Networks.
F. Comellas (*), M. Mitjana (&), J.G. Peters (#)
(*) Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya, Barcelona, Catalonia, Spain
(&) Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya, Barcelona, Catalonia, Spain
(#) School of Computing Science; Simon Fraser University, Burnaby, British Columbia, Canada 
Proceedings 9th Int. Colloquium on Structural Information & Communication Complexity (2002), Eds. C. Kaklamanis and L. Kirousis, Proceedings in Informatics 13, Carleton Scientific, Waterloo 2002 pp. 73-85. ISBN: 1-894145-12-7


The two main characteristics of small-world networks are strong local clustering, and small diameter. These two characteristics are desirable properties in communication networks since typical communication patterns show large amounts of local communication and a small amount of non-local communication that must be completed quickly. In this paper, we study variants of broadcasting that resemble the spread of computer viruses in networks.
Our deterministic results exhibit rates of “infection” that are similar to previously obtained probabilistic results for the spread of contagious diseases populations.

Load a preprint version of the paper: