Abstract
It is believed that almost any pair of people in the world can be connected to one another by a short chain of intermediate acquaintances, of typical length about six. This phenomenon, colloquially referred to as the “six degrees of separation,” has been the subject of considerable recent interest within the physics community. This paper provides a short review of the topic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
L. A. Adamic and B. A. Huberman, Power-law distribution of the world wide web, Science 287:2115a (2000).
R. Albert and A.-L. Barabási, Topology of evolving networks: Local events and universality. Available as cond-mat-0005085 (2000).2
R. Albert, H. Jeong, and A.-L. Barabási, Diameter of the world-wide web, Nature 401:130–131 (1999).
L. A. N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley, Classes of behavior of small-world networks, Proc. Natl. Acad. Sci. 97:11149–11152 (2000).
R. M. Anderson and R. M. May, Susceptible-infectious-recovered epidemic models with dynamic partnerships, J. Math. Biol. 33:661–675 (1995).
P. Bak and K. Sneppen, Punctuated equilibrium and criticality in a simple model of evolution, Phys. Rev. Lett. 71:4083–4086 (1993).
A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286:509–512 (1999).
A.-L. Barabási, R. Albert, and H. Jeong, Mean-field theory for scale-free random networks, Physica A 272:173–187 (1999).
A.-L. Barabási, R. Albert, H. Jeong, and G. Bianconi, Response to “Power-law distribution of the world wide web,” Science 287:2115a (2000).
A. Barrat, Comment on “Small-world networks: Evidence for a crossover picture.” Available as cond-mat-9903323 (1999).
A. Barrat and M. Weigt, On the properties of small-world network models, Europ. Phys. J. B 13:547–560 (2000).
M. Barthélémy and L. A. N. Amaral, Small-world networks: Evidence for a crossover picture, Phys. Rev. Lett. 82:3180–3183 (1999).
B. Bollobás, Random Graphs (Academic Press, New York, 1985).
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, A. Tomkins, and J. Wiener, Graph structure in the web, in Proceedings of the Ninth International World-Wide Web Conference (2000).
R. Das, M. Mitchell, and J. P. Crutchfield, A genetic algorithm discovers particle-based computation in cellular automata, in Parallel Problem Solving in Nature, Y. Davidor, H. P. Schwefel, and R. Manner, eds. (Springer, Berlin, 1994).
M. A. De Menezes, C. F. Moukarzel, and T. J. P. Penna, First-order transition in small-world networks, Europhys. Lett. 50:574–578 (2000).
S. N. Dorogovtsev and J. F. F. Mendes, Exactly solvable small-world network, Europhys. Lett. 50:1–7 (2000).
S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Structure of growing networks. Available as cond-mat-0004434 (2000).
P. Erdös and A. Rényi, On random graphs, Publicationes Mathematicae 6:290–297 (1959).
M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the internet topology, Comp. Comm. Rev. 29:251–262 (1999).
M. E. Fisher and A. N. Berker, Scaling for first-order phase transitions in thermodynamic and finite systems, Phys. Rev. B 26:2507–2513 (1982).
M. Gladwell, Six degrees of Lois Weisberg, The New Yorker 74(41):52–64 (1998).
J. Guare, Six Degrees of Separation: A Play (Vintage, New York, 1990).
S. Jespersen, I. M. Sokolov, and A. Blumen, Small-world Rouse networks as models of cross-linked polymers. Available as cond-mat-0004392 (2000a).
S. Jespersen, I. M. Sokolov, and A. Blumen, Relaxation properties of small-world networks. Available as cond-mat-0004214 (2000b).
R. Kasturirangan, Multiple scales in small-world graphs. Massachusetts Institute of Technology AI Lab Memo 1663. Also cond-mat-9904055 (1999).
M. J. Keeling, The effects of local spatial structure on epidemiological invasions, Proc. Roy. Soc. B 266:859–867 (1999).
D. Kirby and P. Sahre, Six degrees of Monica, New York Times (February 21, 1998).
A. Kleczkowski and B. T. Grenfell, Mean-field-type equations for spread of epidemics: The “small-world” model, Physica A 274:355–360 (1999).
J. Kleinberg, Navigation in a small world, Nature 406:845 (2000).
M. Kocken, The Small World (Ablex, Norwood, New Jersey, 1989).
C. Korte and M. Milgram, Acquaintance linking between white and negro populations: Application of the small world problem, J. Pers. Soc. Psy. 15:101–118 (1970).
P. L. Krapivsky, S. Redner, and F. Leyvraz, Connectivity of growing random networks. Available as cond-mat-0005139 (2000).
M. Kretschmar and M. Morris, Measures of concurrency in networks and the spread of infectious disease, Mathematical Biosciences 133:165–195 (1996).
R. V. Kulkarni, E. Almaas, and D. Stroud, Exact results and scaling properties of small-world networks, Phys. Rev. E 61:4268–4271 (2000).
R. V. Kulkarni, E. Almaas, and D. Stroud, Evolutionary dynamics in the Bak-Sneppen model on small-world networks. Available as cond-mat-9905066 (1999).
L. F. Lago-Fernández, R. Huerta, F. Corbacho, and J. A. Sigüenza, Fast response and temporal coherent oscillations in small-world networks, Phys. Rev. Lett. 84:2758–2761 (2000).
N. Mathias and V. Gopal, Small-worlds: How and why. Available as cond-mat-0002076 (2000).
S. Milgram, The small world problem, Psychology Today 2:60–67 (1967).
R. Monasson, Diffusion, localization and dispersion relations on small-world lattices, Europ. Phys. J. B 12:555–567 (1999).
E. W. Montroll and M. F. Shlesinger, On 1/f noise and other distributions with long tails, Proceedings of the National Academy of Sciences 79:3380–3383 (1982).
C. Moore and M. E. J. Newman, Epidemics and percolation in small-world networks, Phys. Rev. E 61:5678–5682 (2000a).
C. Moore and M. E. J. Newman, Exact solution of site and bond percolation on small-world networks. Phys. Rev. E 62:7059–7064 (2000b).
C. F. Moukarzel, Spreading and shortest paths in systems with sparse long-range connections, Phys. Rev. E 60:6263–6266 (1999).
M. E. J. Newman and G. T. Barkema, Monte Carlo Methods in Statistical Physics (Oxford University Press, Oxford, 1999).
M. E. J. Newman, C. Moore, and D. J. Watts, Mean-field solution of the small-world network model, Phys. Rev. Lett. 84:3201–3204 (2000).
M. E. J. Newman and D. J. Watts, Renormalization group analysis of the small-world network model, Phys. Lett. A 263:341–346 (1999a).
M. E. J. Newman and D. J. Watts, Scaling and percolation in the small-world network model, Phys. Rev. E 60:7332–7342 (1999b).
S. A. Pandit and R. E. Amritkar, Random spread on the family of small-world networks. Available as cond-mat-0004163 (2000).
S. Redner, Random multiplicative processes: An elementary tutorial, Amer. J. Phys. 58: 267–273 (1990).
S. Redner, How popular is your paper? An empirical study of the citation distribution, European Phys. J. B 4:131–134 (1998).
T. Remes, Six Degrees of Rogers Hornsby, New York Times (August 17, 1997).
L. Sattenspiel and C. P. Simon, The spread and persistence of infectious diseases in structured populations, Mathematical Biosciences 90:367–383 (1988).
A. Scala, L. A. N. Amaral, and M. Barthélémy, Small-world networks and the conformation space of a lattice polymer chain. Available as cond-mat-0004380 (2000).
D. Sornette and R. Cont, Convergent multiplicative processes repelled from zero: Power laws and truncated power laws, J. de Physique 17:431–444 (1997).
B. Tjaden and G. Wasson, Available on the internet at http://www.cs.virginia.edu/oracle/ (1997).
T. Valente, Network Models of the Diffusion of Innovations (Hampton Press, Cresskill, New Jersey, 1995).
A. Wagner and D. Fell, The Small World Inside Large Metabolic Networks (University of New Mexico, 2000), preprint.
T. Walsh, in Proceedings of the 16th International Joint Conference on Artificial Intelligence (Stockholm, 1999).
S. Wasserman and K. Faust, Social Network Analysis (Cambridge University Press, Cambridge, 1994).
D. J. Watts, Small Worlds (Princeton University Press, Princeton, 1999).
D. J. Watts and S. H. Strogatz, Collective dynamics of “small-world” networks, Nature 393:440–442 (1998).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Newman, M.E.J. Models of the Small World. Journal of Statistical Physics 101, 819–841 (2000). https://doi.org/10.1023/A:1026485807148
Issue Date:
DOI: https://doi.org/10.1023/A:1026485807148