"Graph Theory in Practice: Part II," by Brian Hayes. AmericanScientist, March/April 2000, pages 104-109.
This continuation of Hayes's article in the January/February 2000 issue ofAmerican Scientistresumes his exploration of mathematical graphs, whichare networks of nodes connected by edges. The article discusses thepeculiarities of "small-world" graphs, which are named, as Hayes explains,"after the familiar cocktail-party experience of making a new acquaintance in adistant city and discovering you have a friend in common." The articledescribes the work of mathematicians Duncan Watts and Stephen Strogatz, whofigured out a way of interpolating between graphs with edges placed in acompletely uniform fashion, and graphs with edges placed in a completely randomfashion. Their methods provide new ways of analyzing small-world graphs.
--- Allyn Jackson