Skip to main content
SpringerLink
Log in

Models of the Small World

  • Published:
Journal of Statistical Physics Aims and scope Submit manuscript

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.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

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).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • R. M. Anderson and R. M. May, Susceptible-infectious-recovered epidemic models with dynamic partnerships, J. Math. Biol. 33:661–675 (1995).

    Google Scholar 

  • P. Bak and K. Sneppen, Punctuated equilibrium and criticality in a simple model of evolution, Phys. Rev. Lett. 71:4083–4086 (1993).

    Google Scholar 

  • A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286:509–512 (1999).

    Google Scholar 

  • A.-L. Barabási, R. Albert, and H. Jeong, Mean-field theory for scale-free random networks, Physica A 272:173–187 (1999).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • M. Barthélémy and L. A. N. Amaral, Small-world networks: Evidence for a crossover picture, Phys. Rev. Lett. 82:3180–3183 (1999).

    Google Scholar 

  • B. Bollobás, Random Graphs (Academic Press, New York, 1985).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • S. N. Dorogovtsev and J. F. F. Mendes, Exactly solvable small-world network, Europhys. Lett. 50:1–7 (2000).

    Google Scholar 

  • 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).

    Google Scholar 

  • M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the internet topology, Comp. Comm. Rev. 29:251–262 (1999).

    Google Scholar 

  • 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).

    Google Scholar 

  • M. Gladwell, Six degrees of Lois Weisberg, The New Yorker 74(41):52–64 (1998).

    Google Scholar 

  • J. Guare, Six Degrees of Separation: A Play (Vintage, New York, 1990).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • J. Kleinberg, Navigation in a small world, Nature 406:845 (2000).

    Google Scholar 

  • M. Kocken, The Small World (Ablex, Norwood, New Jersey, 1989).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • R. V. Kulkarni, E. Almaas, and D. Stroud, Exact results and scaling properties of small-world networks, Phys. Rev. E 61:4268–4271 (2000).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • R. Monasson, Diffusion, localization and dispersion relations on small-world lattices, Europ. Phys. J. B 12:555–567 (1999).

    Google Scholar 

  • 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).

    Google Scholar 

  • C. Moore and M. E. J. Newman, Epidemics and percolation in small-world networks, Phys. Rev. E 61:5678–5682 (2000a).

    Google Scholar 

  • 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).

    Google Scholar 

  • C. F. Moukarzel, Spreading and shortest paths in systems with sparse long-range connections, Phys. Rev. E 60:6263–6266 (1999).

    Google Scholar 

  • M. E. J. Newman and G. T. Barkema, Monte Carlo Methods in Statistical Physics (Oxford University Press, Oxford, 1999).

    Google Scholar 

  • 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).

    Google Scholar 

  • M. E. J. Newman and D. J. Watts, Renormalization group analysis of the small-world network model, Phys. Lett. A 263:341–346 (1999a).

    Google Scholar 

  • M. E. J. Newman and D. J. Watts, Scaling and percolation in the small-world network model, Phys. Rev. E 60:7332–7342 (1999b).

    Google Scholar 

  • 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).

    Google Scholar 

  • S. Redner, How popular is your paper? An empirical study of the citation distribution, European Phys. J. B 4:131–134 (1998).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • 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).

    Google Scholar 

  • D. J. Watts, Small Worlds (Princeton University Press, Princeton, 1999).

    Google Scholar 

  • D. J. Watts and S. H. Strogatz, Collective dynamics of “small-world” networks, Nature 393:440–442 (1998).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico, 87501

    M. E. J. Newman

Authors
  1. M. E. J. Newman
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1026485807148

Search

Navigation