×

Deterministic small-world communication networks. (English) Zbl 1338.68012

Summary: 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 neighbors), 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 “longdistance” 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.

MSC:

68M10 Network design and communication in computer systems
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Albert, R.; Jeong, H.; Barabási, A.-L., Diameter of the world wide web, Nature, Vol. 401, 130-131 (1999)
[2] Barthelemy, M.; Amaral, L. A.N., Small-world networks: Evidence for a crossover picture, Phys. Rev. Lett., Vol. 82, 15, 3180-3183 (1999)
[3] Bermond, J.-C.; Comellas, F.; Hsu, D. F., Distributed loop computer networks: A survey, J. Parallel Distributed Comput., Vol. 24, 2-10 (1995)
[4] Boesch, F. T.; Wang, J. K., Reliable circulant networks with minimum transmission delay, IEEE Trans. Circuits Systems, Vol. CAS-32, 1286-1291 (1985) · Zbl 0583.94018
[5] de Castro, R.; Grossman, J. W., Famous trails to Paul Erdős, Math. Intelligencer, Vol. 21, 3, 51-63 (1999) · Zbl 1052.01519
[6] Herzel, H., How to quantify “small-world” networks?, Fractals, Vol. 6, 4, 301-303 (1998)
[7] Pandit, S. A.; Amritkar, R. E., Characterization and control of small-world networks, Phys. Rev. E, Vol. 60, 2, R1119-R1122 (1999)
[8] Watts, D. J., Small Worlds: The Dynamics of Networks between Order and Randomness (1999), Princeton University Press: Princeton University Press Princeton, NJ
[9] Watts, D. J.; Strogatz, H., Collective dynamics of “small-world” networks, Nature, Vol. 393, 440-442 (1998) · Zbl 1368.05139
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.