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: