Small World Network

Taking a connected graph or network with a high graph diameter and adding a very small number of edges randomly, the diameter tends to drop drastically. This is known as the small world phenomenon. It is sometimes also known as "six degrees of separation" since, in the social network of the world, any person turns out to be linked to any other person by roughly six connections.

Short-term memory uses small world networks between neurons to remember this sentence.

In modern mathematics, the center of the network of coauthorship is considered to be P. Erdős, resulting in the so-called Erdős number. In movies, Kevin Bacon is often mentioned as the center of the movie universe, but a recent study (Reynolds) has shown Christopher Lee to be the actual center. Both actors have co-starred with Julius LeFlore, so the Lee-Bacon distance is two.

REFERENCES

Cohen, P. "Small World Networks Key to Memory." New Scientist 182, 12, 2004. http://www.newscientist.com/news/news.jsp?id=ns99995012.

NIEHS. "Its [sic] a Small World." http://www.niehs.nih.gov/kids/lyrics/smworld.htm.Reynolds, P. "Who is the Center of the Hollywood Universe?" http://www.cs.virginia.edu/oracle/center.html.

Watts, D. J. and Strogatz, S. H. "Collective Dynamics of Small-World Networks." Nature 393, 440-442, 1998. http://tam.cornell.edu/SS_nature_smallworld.pdf.

Watts, D. J. Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton, NJ: Princeton University Press, 1999.Watts, D. J. "Networks, Dynamics, and the Small-World Phenomenon." Amer. J. Soc. 105, 493-527, 1999.