Deterministic Small-World Communication Networks.
F. Comellas (*), J. Ozón (*), J.G. Peters (#)
(*) Departament de Matemàtica Aplicada i Telemàtica; Universitat
Politècnica de Catalunya, Barcelona, Catalonia, Spain
(#) School of Computing Science; Simon Fraser University, Burnaby, British
Columbia, Canada
Information Processing Letters Volume
76, Issue 1-2, 20 November 2000, pages 83-90
Many real life networks, including the world wide web, electric power
grids, and social networks, are small-world networks. The two distinguishing
characteristics of small-world networks are strong local clustering (nodes
have many mutual neighbours), and small average distance between two nodes.
Small-world networks are promising candidates for communication networks
since typical data-flow patterns in communication networks show a large
amount of clustering with a small number of ``long-distance'' communications
that need to be completed quickly. Most previous research on small-world
networks has used simulations, probabilistic techniques, and random replacements
of edges to study the limiting behaviour of these networks. In this paper,
we initiate the study of small-world networks as communication networks
using graph-theoretic methods to obtain exact results. We construct networks
with strong local clustering and small diameter (instead of average distance).
Our networks have the additional property that they are regular.
Load a preprint version of the paper: