×

Deterministic small-world networks. (English) Zbl 0995.60103

Summary: Many real-life networks, such as the World Wide Web, transportation systems, biological or social networks, achieve both a strong local clustering (nodes have many mutual neighbors) and a small diameter (maximum distance between any two nodes). These networks have been characterized as small-world networks and modeled by the addition of randomness to regular structures. We show that small-world networks can be constructed in a deterministic way. This exact approach permits a direct calculation of relevant network parameters allowing their immediate contrast with real-world networks and avoiding complex computer simulations.

MSC:

60K99 Special processes
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Milgram, S., The small-world problem, Psychol. Today, 1, 60-67 (1967)
[2] Bollobás, B.; de la Vega, F., The diameter of random graphs, Combinatorica, 2, 125-134 (1982) · Zbl 0505.05053
[3] Watts, D. J., Small Worlds: The Dynamics of Networks between Order and Randomness (1999), Princeton University Press: Princeton University Press Princeton, NJ
[4] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
[5] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223
[6] Callaway, D. S.; Newman, M. E.J.; Strogatz, S. H.; Watts, D. J., Network robustness and fragility: percolation on random graphs, Phys. Rev. Lett., 85, 5468-5471 (2000)
[7] Albert, R.; Jeong, H.; Barabási, A.-L., Attack and error tolerance in complex networks, Nature, 406, 378-382 (2000)
[8] Comellas, F.; Ozón, J.; Peters, J. G., Deterministic small-world communication networks, Inf. Process. Lett., 76, 83-90 (2000) · Zbl 1338.68012
[9] Amaral, L. A.N.; Scala, A.; Barthélémy, M.; Stanley, H. E., Classes of small-world networks, Proc. Nat. Acad. Sci. USA, 97, 11149-11152 (2000)
[10] Barabási, A.-L.; Ravasz, E.; Vicsek, T., Deterministic scale-free networks, Physica A, 299, 3-4, 559-564 (2001) · Zbl 0972.57003
[11] Albert, R.; Jeong, H.; Barabási, A.-L., Diameter of the world-wide web, Nature, 401, 130-131 (1999)
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.