The small-world phenomenon: an algorithmic perspective. (English) Zbl 1296.05181
Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 163-170 (2000).
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 91D30 | Social networks; opinion dynamics |
References:
| [1] | L. Adamic, “The small world Web,” Proceedings of the European Conf. on Digital Libraries, 1999.]] |
| [2] | R. Albert, H. Jeong, A.-L. Barabasi, “The diameter of the World Wide Web,” Nature 401, 130 (1999).]] |
| [3] | P. Berman, “On-line searching and navigation,” On- Line Algorithms: The State of the Art, A. Fiat and G. Woeginger, Eds., Springer, 1998.]] · Zbl 1177.68009 |
| [4] | B. Bollob s, Random Graphs (Academic Press, London, 1985).]] · Zbl 0567.05042 |
| [5] | B. Bollob s, F.R.K. Chung, “The diameter of a cycle plus a random matching,” SIAM J. Discrete Math. 1, 328 (1988).]] 10.1137/0401033 · Zbl 0664.05036 |
| [6] | F.R.K. Chung, M.R. Garey, “Diameter bounds for altered graphs,” J. Graph Theory 8, 511 (1984).]] · Zbl 0562.05030 |
| [7] | J. Guam, Six Degrees o/Separation: A Play (Vintage Books, New York, 1990).]] |
| [8] | J. Hunter and R. Shotland, “Treating data collected by the small world method as a Markov process,” Social Forces 52, 321 (1974).]] |
| [9] | J. Kaiser, Ed., “It”s a small Web after all,” Science 285, 1815 (1999).]] |
| [10] | P. Killworth and H. Bernard, “Reverse small world experiment,” Social Networks 1,159 (1978).]] |
| [11] | M. Kochen, Ed., The Small World (Ablex, Norwood, 1989).]] |
| [12] | C. Korte and S. Milgram, “Acquaintance networks between racial groups: Application of the small world method,” J. Personality and Social Psych., 15, 101 (1978).]] |
| [13] | S. Milgram, “The small world problem,” Psychology Today 1, 61 (1967).]] |
| [14] | R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, Cambridge, 1095).]] · Zbl 0849.68039 |
| [15] | D. Peleg, E. Upfal, “A trade-off between size and efficiency for routing tables,” Journal of the A CM 36(1989).]] 10.1145/65950.65953 · Zbl 0900.68262 |
| [16] | I. de Sola Pool and M. Kochen, “Contacts and influence,” Social Networks 1, 5 (1978).]] |
| [17] | H. Kautz, B. Selman, M. Shah, “ReferralWeb: Combining Social Networks and Collaborative Filtering,” Communications of the A CM, 30, 3 (March 1997).]] 10.1145/245108.245123 |
| [18] | J. Travers and S. Milgram, “An experimental study of the small world problem,” Sociometry 32, 425 (1969).]] |
| [19] | D. Watts and S. Strogatz, “Collective dynamics of small-world networks,” Nature 393, 440 (1998).]] · Zbl 1368.05139 |
| [20] | H. White, “Search parameters for the small world problem,” Social Forces 49, 259 (1970).]] |
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.
